3.6 列的顺序存储结构★2◎4
3.6 队列的顺序存储结构★2◎4
作为线性表的一种，可以使用数组来实现队列的顺序存储。
1．队列顺序存储结构表示
如下定义了一个数据元素为Elemtype的顺序存储队列的例子：
其中，采用整型front来描述队列头指针，它指向队列中第一个元素，即下一个出队列的元素；整型rear描述队列尾指针，它指向下一个入队列元素的存储位置，如图3-6所示。
如图3-6（c）所示，rear指针已经到达最上端，此时队列“已经用完”，不能再插入数据了。这就是顺序队列的“假溢出”现象，其实在队列的下端还有相当数量的存储空间可供使用。因此，队列的顺序存储结构一般采用“循环队列”的形式：将数组空间看成一个环状，当rear或front到达数组的一端时，让其自动回到数组的另一端，如图3-6（d）所示。
2．循环队列
循环队列仍然使用顺序存储结构，只不过每次进行入队列操作和出队列操作时，指针front和rear不是简单的自加，而是需要判断是否过界（即不能超过QMAXSIZE），一旦过界，就需要重新从0开始。循环队列的示意图如图3-7所示。
3．有关循环队列的判断
如果用C语言来实现循环队列时，则：
队列空的条件是：“front == rear”，如图3-7（b）所示。
队列满的条件也是：“front==rear”，如图3-7（d）所示。
因此，队列满和队列空的条件一模一样，为了能够区分开，有两种折中方案：
（1）记载队列元素数量
在结构QUEUE中增加一个变量count记载队列中的元素数量，初始值为0，每当执行入队列操作时“count++”，每当执行出队列操作时“count–”。如果“front==rear”条件成立，则进一步判断count的取值，当count取值为0时表示队列空，否则队列满。
（2）少用一个元素空间
在循环队列中增加一个不使用的存储空间，当队列中存入了“QMAXSIZE-1”个元素时，即认为循环队列满，不再进行入队列操作，如图3-7（c）所示，此时算式：
成立。
以上两种方法在各种操作下的对比如表3-5所示。
表3-5 两种循环队列实现方法对比表
操 作 | 记载队列元素数量 | 少用一个元素空间 |
| 队列初始化 | front=0;rear=0;count=0 | front=0;rear=0； |
| 队列元素数 | count | (rear-front+QMAXSIZE)%QMAXSIZE |
| 队列空判断 | front==rear && count==0 | front==rear |
| 队列满判断 | front==rear && count!=0 | ((rear+1) % QMAXSIZE)== front |
| 入队列时指针操作 | rear=(rear+1) % QMAXSIZE； count++； | rear=(rear+1) % QMAXSIZE； |
| 出队列时指针操作 | front=(front+1) % QMAXSIZE； count–； | front=(front+1) % QMAXSIZE； |
| 空间复杂度 | 增加一个变量 | 降低了一个单位的存储能力 |
4．入队列操作
数据元素入队列操作过程可分为三个步骤：
①判断队列未满。
②将数组元素Elem[rear]赋值为入队列元素。
③移动队列指针。
以方法2为例，需将队列尾指针增加1，如果指针越界（超过QMAXSIZE）则指针赋值为0。这个操作其实可以使用“取模”运算快速实现，代码为：
以下代码实现队列Q的入队列操作：
5．出队列操作
数据元素的出队列操作过程可分为三个步骤：
① 判断队列未空。
②返回数组元素Elem[front]。
③移动队列指针。
以方法2为例，需将队列头指针指向队列的下一个数据元素，即front取值加1，如果指针越界（超过QMAXSIZE），则指针赋值为0。本次也可以使用“取模”运算，代码为：
以下代码实现队列S的出队列操作：
6．循环队列的特点
（1）由于只在顺序线性表头执行删除操作，在顺序线性表尾执行插入操作，不用数据移动，因此其算法的时间复杂度为常数。
（2）不能随意增加队列的最大存储空间，这样容易造成队列满。
（3）需要一次性分配所需的存储空间，当此队列未达到最大数据元素数时浪费了存储空间。
因此循环队列适用于数据元素总数固定而且数量不大的应用中，比如在DOS下接收键盘输入的缓冲区就是一个循环链表。
3.6 列的顺序存储结构★2◎4