3.6 列的顺序存储结构★2◎4

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