本文目录：一、队列定义二、队列特点三、队列的顺序存储四、队列的链式存储五、循环队列和链式队列比较

队列是做什么用的？

最佳用途当然是模拟现实生活中的队列，如到银行办事要排队，到加油站加油也要排队。在设计呼叫中心程序时，也应用队列用于保存等待帮助的客户——这些客户应该按照他们呼叫的顺序获取帮助。

凡是符合先进先出原则的数学模型，都可以应用队列。最典型的例子是操作系统中用来解决主机与外设之间速度不匹配问题或是多个用户引起资源竞争问题。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

一、队列定义

队列（queue）是一种先进先出的线性表，简称FIFO。在表一端（表尾）插入，在另一端（表头）删除。

二、队列特点

（1）在表一端（表尾）插入，在另一端（表头）删除的线性表。

（2）表的插入操作称为入队，表的取出操作称为出队。

（3）弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。

（4）队列是一种特殊线性表，它的存储结构分为顺序存储（顺序队）和链式存储(链队)，实际上循环顺序队列应用更常见。

（5）队列分为两种：双向队列和单向队列 。

单向队列（队列）：只能在一端删除数据，另一端插入数据。

双向队列（双端队列）：两端都可以进行插入数据和删除数据操作。

三、队列的顺序存储

和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续存储单元依次存放队列头到队列尾的元素之外，还需附设两个整型变量front和rear分别指示队列头元素和队列尾元素位置（分别称头指针和尾指针).

#define MAXQSIZE 100   //队列可能达到的最大长度Typedef struct{QElemType *base;    //存储空间的基地址int front;            // 头指针int rear;             //尾指针}SqQueue;

利用数组实现队列的顺序存储

1.例：a1,a2依次出队

7.1 队列顺序存储

为了在C语言中描述方便起见，在此约定：

初始化创建空队列时，令front=rear=0，每当插入新的队列尾元素时，尾指针rear增1；每当删除队列头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

（1）入队操作时间复杂度为O(1)：每当一个元素入队时，rear会加一。

（2）出队操作时间复杂度为O(n)：每次当一个元素出队时，后面的元素会依次向前移。

2.如何改进出队的时间性能？

放宽队列的所有元素必须存储在数组的前n个单元这一条件，只要求队列的元素存储在数组中连续的位置。设置队头front、队尾rear两个指针：

7.2

约定：队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素。

特点：从队尾依次入队，从队头依次出队，front与rear初始值为-1.

入队：当有数据入队的时候，rear值加一（移到下一个单元），数据放在rear所指向的位置。

出队：当有数据出队的时候，front加一（移到下一个单元），再将front位置上的数据移除。

此时，入队与出队的时间复杂度为O(1)

3.继续入队会出现什么情况？

7.3

假溢出，当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，后面没办法入队，但此时数组的前端还有空闲空间却无法利用，这种现象叫做假溢出。

4.如何解决假溢出？

解决假溢出的办法就是后面满了，我们就再从头开始，也就是首尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

7.4

如下图，假设当前队列分配的最大空间为6，则当队列处于图7.5（d）所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。

7.5

怎样解决这种“假溢出”问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，如图7.6所示，称之为循环队列。

7.6

头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。在图7.7（a）中，队头元素是J5，在元素J6入队之前，在Q.rear的值为5，当元素J6入队之后，通过“模”运算，Q.rear=(Q.rear+1)%6，得到Q.rear的值为0，这样就可以解决图7.5（d）的“假溢出”状态。

7.7

接着在图7.7（b）中，J7、J8、J9、J10相继入队，则队列空间均被占满，此时头、尾指针相同。

在图7.7（c）中，若J5和J6相继从图7.7（a）所示的队列中出队，使队列此时呈“空”的状态，头、尾指针的值也是相同的。

此时问题出来了，当队列空时front==rear；当队列满时，front==rear，那如何判断此时的队列是空还是满？

由此可见，对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。在这种情况下，如何区别队满还是队空呢？通常有以下两种处理方法。

（1）少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是：

队空的条件：Q.front==Q.rear

队满的条件：(Q.rear+1)%MAXQSIZE==Q.front

如图7.7（d）所示，当J7、J8、J9进入图7.7（a）所示的队列后，(Q.rear+1)%MAXQSIZE的值等于Q.front，此时认为队满。

（2）另设一个标志位flag,以区别队列是“空”还是“满”。

下面给出用第一种方法实现循环队列的操作，循环队列的类型定义同前面给出的顺序队列的类型定义。

5.循环队列的操作

（1）循环队列初始化：循环队列的初始化操作就是动态分配一个预定义大小为MAXQSIZE的数组空间。

① 为队列分配一个最大容量为MAXQSIZE的数组空间，base指向数组空间的首地址。

② 头指针和尾指针置为零，表示队列为空。

【算法描述】

Status InitQueue(SqQueue &Q){  Q.base = new QElemType[MAXQSIZE];  If(！Q.base) exit(voerFlow);  Q.front = Q.rear = 0;  Return OK;}

（2）求队列长度：对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。

【算法描述】

int QueueLength(SqQueue Q){   Return(Q.rear-Qfront + MAXQSIZE) % MAXQSIZE}

（3）入队：入队操作是指在队尾插入一个新的元素。

7.8

【算法步骤】

① 判断队列是否满，若满则返回ERROR。

② 将新元素插入队尾。

③ 队尾指针加1。

Status EnQueue(SqQueue &Q,QElemTyep){//尾指针加上1等于头指针，表明队满 If((Q.rear+1)%MAXQSIZE == Q.front)    Return ERROR;Q.base[Q.rear] = e;   //把新元素插入队尾Q.rear = (Q.rear+1)%MAXQSIZE;  //队尾指针加1Return OK;}

（4）出队：出队操作是将队头元素删除。

7.9

【算法步骤】

① 判断队列是否为空，若空则返回ERROR。

② 保存队头元素。

③队头指针加1。

Status DeQueue(SqQueue &Q,QElemType &e){//队空 If(Q.front == Q.rear) return ERROR; e = Q.base[Q.front];   //保存队头元素 Q.front = (Q.front+1)%MAXQSIZE;  //队头指针+1 Return OK;}

（5）取队头元素：当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

Status GetHead(SqQueue Q, QElemType* e) {    // 队列空的标志    if(Q.base == NULL || Q.front == Q.rear) {        return ERROR;    }    *e = Q.base[Q.front];    return OK;}

由上述分析可见，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队。

四、队列链式存储

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，如下图所示。一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。

队列的链式存储结构表示如下：

7.10

Typedef struct QNode{   QElemType data;   Struct QNode *next;}QNode,*QueuePtr;Typedef struct{   QueuePtr front;    //头指针   QueuePtr rear;     //尾指针}LinkQueue;

链队的操作即为单链表插入和删除操作的特殊情况，只是需进一步修改尾指针或头指针。下面给出链队初始化、入队、出队操作的实现。

1、初始化：链队的初始化操作就是构造一个只有一个头结点的空队，如图所示。

7.11

① 生成新结点作为头结点，队头和队尾指针指向此结点。

② 头结点的指针域置空。

【算法描述】

Status InitQueue(LinkQueue* Q) {    if(Q == NULL) {        return ERROR;    }    (*Q).front = (*Q).rear = (QueuePtr) malloc(sizeof(QNode));    if(!(*Q).front) {        exit(OVERFLOW);    }    (*Q).front->next = NULL;    return OK;}

2、入队：和循环队列的入队操作不同的是，链队在入队前不需要判断队是否满，需要为入队元素动态分配一个结点空间，如图（b）和（c）所示。

7.12

【算法步骤】

① 为入队元素分配结点空间，用指针p指向。

② 将新结点数据域置为e。

③ 将新结点插入到队尾。

④ 修改队尾指针为p。

【算法描述】

Status EnQueue(LinkQueue* Q, QElemType e) {    QueuePtr p;        if(Q == NULL || (*Q).front == NULL) {        return ERROR;    }        p = (QueuePtr) malloc(sizeof(QNode));    if(!p) {        exit(OVERFLOW);    }        p->data = e;    p->next = NULL;        (*Q).rear->next = p;    (*Q).rear = p;    return OK;}

3、出队：和循环队列一样，链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放出队头元素的所占空间，如图（d）所示。

7.13

【算法步骤】

① 判断队列是否为空，若空则返回ERROR。

② 临时保存队头元素的空间，以备释放。

③ 修改头结点的指针域，指向下一个结点。

④ 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。

⑤ 释放原队头元素的空间。

Status DeQueue(LinkQueue* Q, QElemType* e) {    QueuePtr p;        if(Q == NULL || (*Q).front == NULL || (*Q).front == (*Q).rear) {        return ERROR;    }        p = (*Q).front->next;    *e = p->data;        (*Q).front->next = p->next;    if((*Q).rear == p) {        (*Q).rear = (*Q).front;    }        free(p);    return OK;}

五、循环队列和链式队列的比较

1、时间复杂度：

循环队列和链式队列的基本操作都需要常数时间O(1)

2、空间复杂度：

循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题

链式队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每一个元素都需要一个指针域，从而产生了结构性开销。