本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.4节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.4队列

3.4.1队列的抽象数据类型定义

队列(queue)是一种先进先出(First In First Out，FIFO)的线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。允许插入的一端称为队尾(rear)，允许删除的一端则称为队头(front)。
在日常生活中有很多这样的例子，如排队买东西，排在队头的先走掉，新来的排在队尾。下面给出队列的抽象数据类型的定义：
ADT Queue{
数据对象：D＝{ai|ai∈ElemSet，i=1，2，…，n，n≥0}
数据关系：R1＝{|ai-1，ai∈D，i=2，…，n}。约定a1端为队列头，an端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
EnQueue(&Q，e)
初始条件：队列Q已存在。
操作结果：插入元素e到队尾。
DeQueue(&Q，&e)
初始条件：队列Q已存在且非空。
操作结果：删除队头元素，用e返回其值。
GetQueue(Q，&e)
初始条件：队列Q已存在且非空。
操作结果：用e返回队头元素。
QueueEmpty(Q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回OK，否则返回FALSE。
DestroyQueue(&Q)
初始条件：队列Q已存在。
操作结果：队列Q被销毁。
}ADT Queue
除了栈与队列之外，还有一种限定性数据结构，这就是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称为端点1和端点2。在实际应用中，还可以有输出受限的双端队列(即一端允许插入和删除，另一端只允许插入的双端队列)和输入受限的双端队列(即一端允许插入和删除，另一端只允许删除的双端队列)。尽管双端队列看起来比栈和队列更灵活，但实际上在应用程序中它远不及栈和队列有用，故在此不作详细讨论。
342队列的链式表示与实现
用链表表示的队列简称为链队列，如图34所示。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)。这里，和单链表一样，为了操作方便起见，我们也为链队列添加一个头结点，并令头指针指向头结点。由此，空队列（如图35a所示）的判定条件为头指针和尾指针均指向头结点。
链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针，图35b～图35d展示了进行这两种操作时指针变化的情况。

链队列类型的说明如下：
typedef struct QNode{//结点类型
ElemTypedata;
struct QNode*next;
}Qnode,*QueuePtr;
typedef struct{//链队列类型
QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
}LinkQueue;
下面给出链队列基本操作的实现。
(1)构造一个空队列
int InitQueue(LinkQueue &Q){//构造一个空队列Q
Q.front=Q.rear=new Qnode;
if(!Q.front)exit(OVERFLOW);//存储分配失败
Q.front->next=NULL;
return OK;
}
(2)销毁队列
int DestryQueue(LinkQueue &Q){//销毁队列Q
while(Q.front){
Q.rear=Q.front->next;
delete(Q.front);
Q.front=Q.rear;
}
return OK;
}
(3)入队操作
int EnQueue(LinkQueue &Q,ElemType e){//插入元素e为Q的新的队尾元素
Qnode *p;
p=new Qnode;
if(!p)exit(OVERFLOW);//存储分配失败
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
(4)出队操作
int DeQueue(LinkQueue &Q,ElemType &e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；

//否则返回ERROR
Qnode *p;
if(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;//当删除的是队列中的最后一个元素时，需对尾指针进行重新赋值

//(指向头结点)
delete p;
return OK;
}

3.4.3队列的顺序表示与实现——循环队列

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放队头到队尾的元素之外，尚需附设两个指针front和rear分别指向队头元素和队尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化队列时，令front=rear=0。每当插入一个新的元素到队尾时，尾指针增1；每当删除队头元素时，头指针增1。因此，在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

假设当前为队列分配的最大空间为6，当front=2，rear=5时，不可再继续插入新的队尾元素，否则会因数组下标越界导致程序代码被破坏，但此时数组中仍然有可用空间。解决这个问题的一个巧妙办法是把顺序队列看做一个环，称为循环队列，指针与元素之间的关系不变。为了避免“队列满”与“队列空”都是“front=rear”的情况，我们采取牺牲一个存储单元的方法来解决：用“队头指针在队尾指针的下一位置”作为“队列满”的标志。循环队列的示意图如图36所示。
循环队列的类型定义如下：

define MAXSIZE100//最大队列长度

typedef struct{
ElemType*base;//动态分配存储空间
intfront;//头指针，若队列不空，指向队列头元素
intrear;//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;
下面给出循环队列的各种操作。
(1)构造一个空循环队列
int InitQueue(SqQueue &Q){//构造一个空循环队列Q
Q.base=new ElemType［MAXSIZE］;
if(!Q.base)exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
(2)求循环队列的长度
int QueueLength(SqQueue Q){
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
(3)插入元素e为Q的新的队尾元素
int EnQueue(SqQueue &Q,ElemType e){//插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//队列满
Q.base［Q.rear］=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}
(4)删除Q的队头元素
int DeQueue(SqQueue &Q,ElemType &e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR
if(Q.front==Q.rear)return ERROR;//队列空
e=Q.base［Q.front］;
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}
344队列的应用举例
队列在计算机科学领域的应用非常广泛，例如，解决主机与外部设备之间速度不匹配的问题。主机输出数据给打印机打印，输出数据的速度比打印机打印数据的速度要快得多。若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。因此，解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入到这个缓冲区中，写满后就暂停写入，转去做其他的事情；打印机从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出申请，主机接到申请后再向缓冲区写入打印数据，这样做既保证了打印数据的正确，又提高了主机的效率。由此可见，打印数据的缓冲区就是一个队列。下面再以舞伴问题为例介绍队列的应用。
假设在周末舞会上，男士和女士进入舞厅时，各自排成一队。开始跳舞时，依次从男队和女队的队头各自出一个人配成舞伴。若两队的初始人数不相同，则较长的那一队中未配对者等待下一支舞曲。现要求编写一个算法模拟上述舞伴配对问题。
由于先入队的男士或女士亦先出队配成舞伴，所以该问题具有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某个队列变空为止。此时，某队仍有等待的配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他(或她)将是下一支舞曲开始时第一个可获得舞伴的人。
数据结构定义如下：
Typedef struct{
char name［20］;
char sex;//'F'表示女性，'M'表示男性
}ElemType;
算法描述如下：
void DanceParter(ElemType dancer［］,int num){
int i;
ElemType p,e;
SqQueue Mdancers,Fdancers;
InitQueue(Mdancers);
InitQueue(Fdancers);
for(i=0;ip=dancer［i］;
if(p.sex=='F')EnQueue(Fdancers,p);
else EnQueue(Mdancers,p);
}
while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)){
DeQueue(Fdancers,e);
printf("%s(%c)与",e.name,e.sex);
DeQueue(Mdancers,e);
printf("%s(%c)配对\\n",e.name,e.sex);
}
if(!QueueEmpty(Fdancers)){
printf("女队等待人数为%d,",(Fdancers.rear-Fdancers.front)%MAXSIZE);
GetQueue(Fdancers,p);
printf("第一个等待者为%s\\n",p.name);
}
if(!QueueEmpty(Mdancers)){
printf("男队等待人数为%d",(Mdancers.rear-Mdancers.front)%MAXSIZE);
GetQueue(Mdancers,p);
printf("第一个等待者为%s\\n",p.name);
}
}