队列，我何时才能排到队头呢？

队列，我何时才能排到队头呢？-五分钟学算法

00.
队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

与栈相反，队列是一种先进先出（First In First Out，FIFO）的线性表。

与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表和链表作为基础。

我们的输入缓冲区接收键盘的输入就是按照队列的形式输入和输出的，不然的话就很容易出问题。

01.
队列的链式存储结构队列既可以用链表来实现，也可以用顺序表来实现，跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称链队列。

typedef struct QNode {
ElemType data;
struct QNode *next;
}QNode, *QueuePrt;

typedef struct {
QueuePrt front,rear; //对头与队尾指针
} LinkQueue;

我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。（注：头结点不是必须的，但是为了方便操作，我们加上了）

空队列的时候，front和rear都指向头结点

创建一个队列

创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，此时生成一个空队列。

initQueue(LinkQueue *q)
{
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
if( !q->front)
exit(0)
q->front->next = NULL;
}

入队列操作

入队列操作过程如下：

出队列操作

出队列操作就是将队列中的第一个元素移动，队头指针不发生变化，改变头结点的next指针即可。

出队列的操作过程如下：

如果原队列中只有一个元素，那么我们就应该处理一下队尾指针。

DeleteQueue(LinkQueue *q, ElemType *e)
{
QueuePtr p;
if( q->front == q->rear )
{
return;
}
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if( q->rear == p)
q->rear = q->front;
free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它销毁掉，以免过多地占用内存空间。

DestroyQueue(LinkQueue *q)
{
    while(q->front) {
        q->rear = q->front->next;
        free(q->front);
        q->front=q->rear;
    }
}

02.

队列的顺序存储结构

队列更适合用链式存储结构来实现。假设一个队列有n个元素，则顺序存储结构的队列需要建立一个大于n的存储单元，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端则是队头。

入队列的操作其实就是在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)；出队列则不同，因为我们已经假设下标为0的位置是队列的对头，因此每次出队列操作所有的元素都要向前移动。这样一来出队列的时间复杂度为O(n)，效率大打折扣。

在现实中也是如此，一群人在排队买火车票，前边的人买好了离开，后面的人就要全部向前一步补上空位。

可是我们研究数据结构与算法的一个根本目的就是要想方设法提高我们的程序的效率，按照下标为0的一端为队头，且队头不变，出队列的时间复杂度是O(n)，效率大打折扣！

如果不去限制队头一定要在下标为0的位置，那么出队列的操作就不需要移动全体元素。

上面的动画中三个元素出队之后，当我们要插入一个元素时，我们已知队列最多可以放6个元素，现在队列中只有三个，这样程序试图将新的元素入队就会出现假溢出的错误。

为了解决假溢出的问题，当数组后面满了，就再从头开始，也就是头尾相接的循环。循环队列的容量固定，并且它的队头和队尾指针都可以随着元素出入队列而发生改变，这样循环队列逻辑上就好像是一个环形存储空间。

但在实际的内存中，不可能有真正的环形存储区，我们只能用顺序表来模拟出来逻辑上的循环。

定义一个循环队列

#define MAXSIZE 100
typedef struct
{
ElemType *base; //用于存放内存分配基地址
int front;
int rear;
}

初始化一个循环队列

initQueue(cycleQueue *q)
{
q->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
if( !q->base )
exit(0);
q->front = q->rear = 0;
}

入队列操作

InsertQueue(cycleQueue *q, ElemType e)
{
if( (q->rear+1)%MAXSIZE == q->front ) //判断是否满了
return; //队列已满
q->base[q->rear] = e;
q->rear = (q->rear+1) % MAXSZIE;
}

出队列操作

DeleteQueue(cycleQueue *q, ElemType *e)
{
if( q->front == q->rear ) //判断队列是否为空
{
return;
}
*e = q->base[q->front];
q->front = (q->front + 1) % MAXSIZE;

END

作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。