3.4.2　队列的顺序存储

1．顺序队列的“假溢出”

在对顺序队列进行插入和删除操作的过程中，可能会出现“假溢出”现象。经过多次插入和删除操作后，实际上队列还有存储空间，但是又无法向队列中插入元素，我们将这种溢出称为“假溢出”。

例如，在图3-15所示的队列中插入3个元素h、i、j，然后删除2个元素a、b，就会出现如图3-16所示的情况。当插入元素j后，队尾指针rear将越出数组的下界而造成“假溢出”。

2．顺序循环队列的表示

为了避免出现顺序队列的“假溢出”，通常采用顺序循环队列实现队列的顺序存储。

（1）顺序循环队列

为了充分利用存储空间，消除这种“假溢出”现象，当队尾指针rear和队头指针front到达存储空间的最大值（假定队列的存储空间为QueueSize）的时候，让队尾指针和队头指针转化为0，这样就可以将元素插入到队列还没有利用的存储单元中。在图3-16中，插入元素j之后，将rear变为0，则可继续将元素插入下标为0的存储单元中。这样就把顺序队列使用的存储空间构造成一个逻辑上首尾相连的循环队列。

当队尾指针rear达到最大值QueueSize-1时，若要插入元素（若队列中还有存储空间），就要把队尾指针rear变为0；当队头指针front达到最大值QueueSize-1时，若要将队头元素出队，要让队头指针front变为0。这可通过取余操作实现队列的首尾相连。例如，假设QueueSize=10，当队尾指针rear=9时，若要将新元素入队，则先令rear=（rear+1）%10=0，然后将元素存入队列的第0号单元，通过取余操作实现了队列的逻辑上的首尾相连。

（2）顺序循环队列的队空和队满判断

但是，在顺序循环队列在队空和队满的情况下，队头指针front和队尾指针rear同时都会指向同一个位置，即front==rear，如图3-17所示。即队列为空时，有front=0、rear=0，因此front==rear；队满时也有front=0、rear=0，因此front==rear。

为了区分队空还是队满，通常采用如下两个方法。

（1）增加一个标志位。设这个标志位为flag，初始时，有flag=0；当入队列成功，则flag=1；出队列成功，则flag=0。因此，队列为空的判断条件为front==rear&&flag==0，队列满的判断条件为front==rear&&flag==1。

（2）少用一个存储单元。队空的判断条件为front==rear，队满的判断条件为front==（rear+1）%QueueSize。那么，入队的操作语句为rear=（rear+1）%QueueSize，Q［rear］=x。出队的操作语句为front=（front+1）%QueueSize。少用一个存储单元的顺序循环队列队满情况如图3-18所示。

顺序循环队列类型描述如下：

其中，queue用来存储队列中的元素，front和rear分别表示队头指针和队尾指针，取值范围为0~QueueSize。

顺序循环队列的主要操作说明如下：

（1）初始化时，设置SQ.front=SQ.rear=0。

（2）循环队列队空的条件为SQ.front==SQ.rear，队满的条件为SQ.front==（SQ.rear+1）%QueueSize。

（3）入队操作时，先判断队列是否已满，若队列未满，则将元素值e存入队尾指针指向的存储单元，然后将队尾指针加1后取模。

（4）出队操作时，先判断队列是否为空，若队列不空，则先把队头指针指向的元素值赋给e，即取出队头元素，然后将队头指针加1后取模。

（5）循环队列的长度为（SQ.rear+QueueSize-SQ.front）%QueueSize。

3．顺序循环队列的基本运算

（1）初始化。

（2）判断队列是否为空。若队头指针与队尾指针相等，则队列为空，否则队列不为空。算法实现如下：

（3）将元素e入队。在将元素入队（即把元素插入到队尾）之前，先判断队列是否已满。如果队列未满，则执行插入运算，然后队尾指针加1把队尾指针向后移动。入队操作的算法实现如下：

（4）将队头元素出队。在队头元素出队（即删除队头元素）之前，先判断队列是否为空。若队列不空，则删除队头元素，然后将队头指针向后移动，使其指向下一个元素。出队操作的算法实现如下：

（5）取队头元素。先判断顺序循环队列是否为空，如果队列为空，则返回0表示取队头元素失败；否则，把队头元素赋给e，并返回1表示取队头元素成功。取队头元素的算法实现如下：

（6）清空队列，算法实现如下：