本节书摘来自华章出版社《数据结构与算法 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){//构造一个空队列QQ.front=Q.rear=new Qnode;if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;return OK;}(2)销毁队列int DestryQueue(LinkQueue &Q){//销毁队列Qwhile(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；

//否则返回ERRORQnode *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){//构造一个空循环队列QQ.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；//否则返回ERRORif(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);}}