高薪算法+计算机职称考试数据结构与算法算法

数据结构-队列

2019-04-24  本文已影响0人  1江春水

队列

队列的基本概念

  1. 队列是有限个同类型元素的线性序列
  2. 队列也是一种运算受限的线性表,而且是先进先出的线性表 FIFO
  3. 新加入的数据元素加入在队尾,出队列的数据元素在队列首部被删除

如下图所示


屏幕快照 2019-04-24 16.49.55.png

队列的基本运算

  1. 队列初始化
  2. 队列判空
  3. 入队
  4. 出队
  5. 取队列首元素
  6. 清空队列
  7. 销毁队列
  8. 获取队列长度

队列的两种存储结构

顺序存储

先看一个图:


屏幕快照 2019-04-24 17.24.59.png

从上图看出,随着队列的入队、出队进行,会使整体队列向上移动(也就是向后移动),当队尾指针指向最上端的存储区域时,就不能入队了,再入队会出现溢出,但是实际上队列中还有空余空间;这种现象称为"假溢出"。
解决假溢出的方法:

  1. 方法一:每次队列出队时,让队列整体向前移动一个位置,这样就保证了队首元素始终在最前边(存储空间的首个元素地址);但是这样每次都需移动N个元素,平均时间复杂度为O(n);效率低
  2. 方法二:当队尾出现溢出时,可判断头指针位置,如果前边有空余位置,则把当前队列整体前移,这样可减少元素的移动次数,可以看做是方法一的优化;
  3. 方法三:引入循环队列的概念。可以将队列看成首尾相接的循环结构,当队尾指针到队尾后,再从头指针开始;这种方法就不需要移动元素了,这种顺序队列称为循环队列。
循环队列

当使用了循环队列,入队的队尾指针加1操作及出队的队首指针加1操作要做响应的修改,当front==rear时,有可能是空队列,也有可能队列已满,为了区分开,队列最多可容纳maxsize-1个元素。

循环队列 C语言实现

const int maxsize = 10;

typedef struct queue {
    int front;
    int rear;
    int data[maxsize];//数据为int类型
}CycleQueue;

1、队列初始化

CycleQueue *initCycleQueue() {
    CycleQueue *queue = (CycleQueue *)malloc(sizeof(CycleQueue));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

2、 队列判空

int emptyQueue(CycleQueue *queue) {
    if (queue->front == queue->rear) {
        return 1;
    }
    return 0;
}

3、入队

int enQueue(CycleQueue *queue,int x) {
    if ((queue->rear+1) % maxsize == queue->front) {
        printf("队列已满");
        return 0;
    } else {
        queue->rear = (queue->rear+1) % maxsize;
        queue->data[queue->rear] = x;
        return 1;
    }
}

4、出队

int outQueue(CycleQueue *queue) {
    if (emptyQueue(queue)) {
        printf("队列为空");
        return 0;
    } else {
        queue->front = (queue->front+1) % maxsize;
        return 1;
    }
}

5、取队列首元素

int getFirst(CycleQueue *queue) {
    if (emptyQueue(queue)) {
        printf("队列为空");
        return -1;
    } else {
        return queue->data[queue->front+1];
    }
}

6、清空队列

void clearQueue(CycleQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

7、销毁队列

void destoryQueue(CycleQueue *queue) {
    free(queue);
    queue = NULL;
}

8、获取队列长度

int lengthQueue(CycleQueue *queue) {
    return (queue->rear-queue->front+maxsize) % maxsize;
}
链队列

。。。

上一篇 下一篇

猜你喜欢

热点阅读