本节书摘来自华章出版社《数据结构与算法 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。在实际应用中,还可以有输出受限的双端队列(即一端允许插入和删除,另一端只允许插入的双端队列)和输入受限的双端队列(即一端允许插入和删除,另一端只允许删除的双端队列)。尽管双端队列看起来比栈和队列更灵活,但实际上在应用程序中它远不及栈和队列有用,故在此不作详细讨论。
342队列的链式表示与实现
用链表表示的队列简称为链队列,如图34所示。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)。这里,和单链表一样,为了操作方便起见,我们也为链队列添加一个头结点,并令头指针指向头结点。由此,空队列(如图35a所示)的判定条件为头指针和尾指针均指向头结点。
链队列的操作即为单链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针,图35b~图35d展示了进行这两种操作时指针变化的情况。
链队列类型的说明如下:
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。因此,在非空队列中,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一个位置。
![8ad723d3a1bbd9f1eb141976d5dc81c79f6223b0](https://yqfile.alicdn.com/8ad723d3a1bbd9f1eb141976d5dc81c79f6223b0.png?x-oss-process=image/resize,w_1400/format,webp)
假设当前为队列分配的最大空间为6,当front=2,rear=5时,不可再继续插入新的队尾元素,否则会因数组下标越界导致程序代码被破坏,但此时数组中仍然有可用空间。解决这个问题的一个巧妙办法是把顺序队列看做一个环,称为循环队列,指针与元素之间的关系不变。为了避免“队列满”与“队列空”都是“front=rear”的情况,我们采取牺牲一个存储单元的方法来解决:用“队头指针在队尾指针的下一位置”作为“队列满”的标志。循环队列的示意图如图36所示。
循环队列的类型定义如下:
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;
}
344队列的应用举例
队列在计算机科学领域的应用非常广泛,例如,解决主机与外部设备之间速度不匹配的问题。主机输出数据给打印机打印,输出数据的速度比打印机打印数据的速度要快得多。若直接把输出的数据送给打印机打印,由于速度不匹配,显然是不行的。因此,解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依次写入到这个缓冲区中,写满后就暂停写入,转去做其他的事情;打印机从缓冲区中按照先进先出的原则依次取出数据并打印,打印完后再向主机发出申请,主机接到申请后再向缓冲区写入打印数据,这样做既保证了打印数据的正确,又提高了主机的效率。由此可见,打印数据的缓冲区就是一个队列。下面再以舞伴问题为例介绍队列的应用。
假设在周末舞会上,男士和女士进入舞厅时,各自排成一队。开始跳舞时,依次从男队和女队的队头各自出一个人配成舞伴。若两队的初始人数不相同,则较长的那一队中未配对者等待下一支舞曲。现要求编写一个算法模拟上述舞伴配对问题。
由于先入队的男士或女士亦先出队配成舞伴,所以该问题具有典型的先进先出特性,可用队列作为算法的数据结构。在算法中,假设男士和女士的记录存放在一个数组中作为输入,然后依次扫描该数组的各元素,并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后,依次将两队当前的队头元素出队来配成舞伴,直至某个队列变空为止。此时,某队仍有等待的配对者,算法输出此队列中等待者的人数及排在队头的等待者的名字,他(或她)将是下一支舞曲开始时第一个可获得舞伴的人。
数据结构定义如下:
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);
}
}