数据结构-队列

队列

队列的基本概念

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;
}

链队列

。。。