3.2 队列
3.2.1 队列的基本概念
队列（简称队）也是一种运算受限的线性表，在这种特殊的线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。队列的插入操作称为进队，删除操作称为出队。允许插入的一端称为队尾，允许删除的一端称为队头。新插入的元素只能添加到队尾，被删除的只能是排在队头的元素。
正是这种受限的元素插入和删除运算，使得队列表现出先进先出或者后进后出的特点。举一个例子进行说明，如图3.13所示是顾客①～⑤排队买车票的情况，排队围栏里能容纳若干人，但每次只能容许一个人进出，进入排队队列只能从进口进，某顾客买完车票后只能从出口出。从中看到，顾客进入排队队列的顺序是①～⑤，那么买票并离开队列的顺序也只能是①～⑤。也就是说，顾客进出排队队列的原则是先进去的先出来。
归纳起来，一个队列的示意图如图3.14所示。
图3.13 顾客排队买车票
图3.14 队列的示意图
队列的基本运算如下。
（1）初始化队列InitQueue（qu）：建立一个空队qu。
（2）销毁队DestroyQueue（qu）：释放队列qu占用的内存空间。
（3）进队EnQueue（qu，x）：将x插入到队列qu的队尾。
（4）出队DeQueue（qu，x）：将队列qu的队头元素出队并赋给x。
（5）取队头元素GetHead（qu，x）：取出队列qu的队头元素并赋给x，但该元素不出队。
（6）判断队空QueueEmpty（qu）：判断队列qu是否为空。
包含基本运算的队列如图3.15所示，其中，op1～op6表示上述6个基本运算。
图3.15 包含基本运算的队列
【例3.10】以下属于队列的基本运算的是________。
A．对队列中的元素排序
B．取出最近进队的元素
C．在队列中某元素之前插入元素
D．删除队头元素
解：删除队头元素即出队，属队列的一种基本运算，其他均不是队列的基本运算。本题答案为D。
【例3.11】设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b、d、c、f、e、a、g，则栈S的容量至少是________。
A．1
B．2
C．3
D．4
解：由于队列不改变进、出队元素的次序，即a1、a2、…、an依次进入一个队列，出队序列只有a1、a2、…、an一种，所以本题变为通过一个栈将a、b、c、d、e、f、g序列变为b、d、c、f、e、a、g序列时栈空间至少多大。其过程如表3.1所示，从中可以看到，栈中最多有三个元素，即栈大小至少为3。本题答案为C。
表3.1 由a、b、c、d、e、f、g序列通过一个栈得到b、d、c、f、e、a、g序列的过程
3.2.2 队列的顺序存储结构
与栈类似，队列通常有两种存储结构，即顺序存储结构和链式存储结构。队列的顺序存储结构简称为顺序队，它由一个一维数组（用于存储队列中元素）及两个分别指示队头和队尾的变量组成（因为队列不同于栈，栈只要一端发生改变，而队列的两端都可能发生改变），这两个变量分别称为“队头指针”和“队尾指针”。通常约定队尾指针指示队尾元素的当前位置，队头指针指示队头元素的前一个位置。
顺序队的类型声明如下。
顺序队的定义为一个结构类型，该类型变量有三个域：data、front、rear。其中，data为存储队列中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围是0～MaxSize—1。
图3.16表示了顺序队列sq（假设MaxSize=5）的几种状态。
图3.16（a）表示队列的初始状态，sq.rear=sq.front=—1。
图3.16（b）表示元素a进队后，sq.rear=0，sq.front=—1。
图3.16（c）表示元素b、c、d、e依次进队后，sq.rear=4，sq.front=—1。
图3.16（d）表示元素a、b出队后，sq.rear=4，sq.front=1。
图3.16（e）表示元素c、d、e出队后，sq.rear=sq.front=4。
图3.16 顺序队的几种状态
从图3.16中可以看到，在队列刚建立时，先对它进行初始化，令front=rear=—1。每当进队一个元素时，让队尾指针rear增1，再将新元素放在rear所指位置，也就是说元素进队只会引起rear的变化，而不会导致front的变化，而且rear指示刚进队的元素（队尾元素）位置。队头指针front则不同，每当出队一个元素时，让队头指针front增1，再把front所指位置上的元素取出，也就是说元素出队只会引起front的变化，而不会导致rear的变化，而且front所指示的元素已出队了，它实际指示的是当前队列中队头元素的前一位置。
从图3.16中可以看到，图3.16（a）和图3.16（e）都是队空的情况，均满足front==rear的条件，所以可以将front==rear作为队空的条件。那么队满的条件如何设置呢？受顺序栈的启发，似乎很容易得到队满的条件为rear==MaxSize—1。显然这里有问题，因为图3.16（d）和图3.16（e）都满足这个“队满”的条件，而实际上队列并没有满，这种因为队满条件设置不合理而导致的“溢出”称为假溢出，也就是说这种“溢出”并不是真正的溢出，尽管队满条件成立了，但队列中还有多个存放元素的空位置。
为了能够充分地使用数组中的存储空间，可以把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环，这个环形的表叫作循环队列或环形队列。图3.17表示了循环队列sq的几种状态。
图3.17（a）表示队列的初始状态，sq.rear=sq.front=0。
图3.17（b）表示元素a进队后，sq.rear=1，sq.front=0。
图3.17（c）表示元素b、c、d、e依次进队后，sq.rear=0，sq.front=0。
图3.17（d）表示元素a、b出队后，sq.rear=0，sq.front=2。
图3.17（e）表示元素c、d，e出队后，sq.rear=sq.front=0。
图3.17 循环队列的几种状态
循环队列首尾相连，当队头指针front==MaxSize—1后，再前进一个位置就自动到0，这可以利用除法取余的运算（MOD，C/C++语言中运算符为%）来实现。所以队头队尾指针进1的操作如下。
队头指针进1：front=（front+1）MOD MaxSize
队尾指针进1：rear=（rear+1）MOD MaxSize
循环队列的队头指针和队尾指针初始化时都置为0：front=rear=0。在队尾插入新元素和删除队头元素时，相关指针都循环进1。当它们进到MaxSize—1时，并不表示队空间满了，只要有需要，利用MOD运算可以前进到数组的0号位置。
如果循环队列读取元素的速度快于存入元素的速度，队头指针会很快追上队尾指针，一旦到达front==rear时，则队列变成空队列。反之，如果队列存入元素的速度快于读取元素的速度，队尾指针很快就会赶上队头指针，一旦队列满就不能再加入新元素了。
在循环队列中仍不能区分队空和队满，因为图3.17（a）、图3.17（c）和图3.17（e）都满足条件front==rear，而图3.17（a）和图3.17（e）为队空，图3.17（c）为队满。那么如何解决这一问题呢？仍设置队空条件为front==rear，将队满条件设置为（rear+1）MOD MaxSize== front，也就是说，当rear指到front的前一位置时就认为队列满了，显然在这样设置的队满条件下，队满条件成立时队中还有一个空闲单元，也就是说这样的队中最多只能进队MaxSize—1个元素。
说明：上述设置循环队列队满条件的方法不是最理想的，因为队中最多只能放入MaxSize—1个元素，但它是一种最简单的方法，后面例3.15就在这个基础上进行了改进，读者可以体会两种方法的差异。
归纳起来，上述设置的循环队列sq的4个要素如下。
（1）队空条件：sq.front==sq.rear。
（2）队满条件：（sq.rear+1）%MaxSize==sq.front。
（3）进队操作：sq.rear循环进1；元素进队。
（4）出队操作：sq.front循环进1；元素出队。
循环队列的基本运算算法如下。
1．初始化队列运算算法
其主要操作是：设置sq.front=sq.rear=0。对应的算法如下。
2．销毁队列运算算法
这里顺序队的内存空间是由系统自动分配的，在不再需要时由系统自动释放其空间。对应的算法如下。
void DestroyQueue(SqQueue sq)
{ }
3．进队运算算法
其主要操作是：先判断队列是否已满，若不满，让队尾指针循环进1，在该位置存放x。对应的算法如下。
4．出队运算算法
其主要操作是：先判断队列是否已空，若不空，让队头指针循环进1，将该位置的元素值赋给x。对应的算法如下。
5．取队头元素运算算法
其主要操作是：先判断队列是否已空，若不空，将队头指针前一个位置的元素值赋给x。对应的算法如下。
6．判断队空运算算法
其主要操作是：若队列为空，则返回1；否则返回0。对应的算法如下。
int QueueEmpty(SqQueue sq)
{ if(sq.rear==sq.front)return 1;
else return 0;
}
提示：将顺序队类型声明及其基本运算函数存放在SqQueue.cpp文件中。
当顺序队的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序队的各种运算的实现过程。
上述程序的执行结果如图3.18所示。
图3.18 程序的执行结果
说明：顺序队有循环队列和非循环队列两种，前者把存储队列元素的表从逻辑上看成一个环，从而新进队的元素可以覆盖已出队元素的空间，提高存储空间利用率。但有些情况下要利用所有进队的元素求解时，只能采用非循环队列。
【例3.12】若用一个大小为6的数组来实现循环队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为________。
A．1和5
B．2和4
C．4和2
D．5和1
解：当前有rear=0，进队两个元素后，rear循环递增2，rear=2；当前有front=3，出队一个元素后，front循环递增1，front=4。本题答案为B。
【例3.13】对于循环队列，写出求队列中元素个数的公式，并编写相应的算法。
解：循环队列中队头、队尾指针变化主要有如图3.19所示的两种情况，归纳起来，循环队列元素个数的计算公式如下。
图3.19 求循环队中元素个数的两种情况
（rear—front+MaxSize）%MaxSize
对应的算法如下。
int Count(SqQueue sq)
{
return(sq.rear—sq.front+MaxSize) % MaxSize;
}
【例3.14】已知循环队列存储在一维数组A[0..n—1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是________。
A．0，0
B．0，n—1
C．n—1，0
D．n—1，n—1
解：在循环队列中，进队操作是队尾指针rear循环加1，再在该处放置进队的元素，本题要求第一个进入队列的元素存储在A[0]处，则rear应为n—1，因为这样有（rear+1）%n=0。而队头指针front指向队头元素，此时队头位置为0，所以front的初值为0。本题答案为B。
提示：在一般的数据结构教科书中，循环队列的队头指针front设计为指向队列中队头元素的前一个位置，而队尾指针rear指向队尾元素的位置，本题的front和rear有所不同。
【例3.15】如果用一个大小为MaxSize的数组表示环形队列，该队列只有一个队头指针front，不设队尾指针rear，而改置一个计数器count，用以记录队列中的元素个数。
（1）队列中最多能容纳多少个元素？
（2）设计实现队列基本运算的算法。
解：依题意，设计队列的类型如下。
（1）队列中最多可容纳MaxSize个元素，因为这里不需要空出一个位置以区分队列空和队列满的情况。
（2）队列sq为空的条件是：sq.count==0；队列为满的条件是：sq.count==MaxSize。在队头指针sq.front和队中元素个数sq.count已知时，计算队尾元素的位置的公式是：
队尾元素位置=（sq.front+sq.count）%MaxSize
在这种队列上实现队列的基本运算算法如下。
3.2.3 队列的链式存储结构
队列的链式存储结构简称为链队，它实际上是一个同时带有队头指针front和队尾指针rear的单链表。队头指针指向队头结点，队尾指针指向队尾结点即单链表的最后一个结点，并将队头和队尾指针结合起来构成链队结点，如图3.20所示。
图3.20 链队示意图
其中，链队的数据结点类型声明如下。
链队结点的类型声明如下。
在这样的链队中，队空的条件是lq—>front==NULL或lq—>rear==NULL（这里采用lq—>front==NULL的队空条件）。一般情况下，链队是不会出现队满的情况的。归纳起来，链队lq的4个要素如下。
（1）队空条件：lq—>front==NULL。
（2）队满条件：不考虑（因为每个结点是动态分配的）。
（3）进队操作：创建结点p，将其插入到队尾，并由lq—>rear指向它。
（4）出队操作：删除队头结点。
在链队上实现队列基本运算算法如下。
1．初始化队列运算算法
其主要操作是：创建链队结点，并置该结点的rear和front均为NULL。对应的算法如下。
2．销毁队列运算算法
链队的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间。在销毁队列lq时，先像释放单链表一样释放队中所有数据结点，然后释放链队结点lq。对应的算法如下。
3．进队运算算法
其主要操作是：创建一个新结点s，将其链接到链队的末尾，并由rear指向它。对应的算法如下。
4．出队运算算法
其主要操作是：将front指向结点的data域值赋给x，并删除该结点。对应的算法如下。
5．取队头元素运算算法
其主要操作是：将front指向结点的data域值赋给x。对应的算法如下。
6．判断队空运算算法
其主要操作是：若链队为空，则返回1；否则返回0。对应的算法如下。
提示：将链队结点类型声明及其基本运算函数存放在LinkQueue.cpp文件中。
当链队的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会链队的各种运算的实现过程。
上述程序的执行结果如图3.18所示。
【例3.16】若使用不带头结点的循环链表来表示队列，lq是这样的链表中尾结点指针，如图3.21所示。试基于此结构给出队列的相关运算算法。
图3.21 用循环单链表表示链队
解：这里使用的循环链表不带头结点，lq始终指向队尾结点，lq—>next即为队头结点。当lq==NULL时队列为空，lq—>next==lq表示队列中只有一个结点。队列的相关运算算法如下。
【例3.17】以下各种不带头结点的链表中最不适合用作链队的是________。
A．只带队首指针的非循环双链表
B．只带队首指针的循环双链表
C．只带队尾指针的循环双链表
D．只带队尾指针的循环单链表
解：队列最基本的运算是进队和出队。链队的队头和队尾分别在链表的前、后端，即进队在链尾进行，出队在链首进行。
对于选项A的只带队首指针的非循环双链表，在末尾插入一个结点（进队）的时间复杂度为O（n），其他选项的链表完成同样操作的时间复杂度均为O（1），所以相比较而言，选项A的存储结构最不适合用作链队。本题答案为A。
3.2.4 队列的应用示例
在较复杂的数据处理过程中，通常需要保存多个临时产生的数据，如果先产生的数据先进行处理，那么需要用队列来保存这些数据。下面通过一个典型示例说明队列的应用。
【例3.18】设计一个程序，反映病人到医院看病、排队看医生的过程。
解：（1）设计存储结构。
病人排队看医生采用先到先看的方式，所以要用到一个队列。由于病人人数具有较大的不确定性，这里采用一个带头结点的单链表作为队列的存储结构。为了简单，病人通过其姓名来唯一标识。例如，有Smith、John和Mary三个病人依次排队的病人队列如图3.22所示。
图3.22 病人队列
病人链队结点类型如下。
病人链队中的结点类型如下。
（2）设计运算算法。
在病人队列设计好后，设计相关的基本运算算法，如队列初始化、进队和出队等，这些算法如下。
（3）设计主函数。
然后设计如下主函数通过简单的提示性菜单方式来操作各个功能。
（4）执行结果。
本程序的一次执行结果如图3.23所示。
图3.23 看病程序的一次执行结果