3.4.4 顺序循环队列

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

1.顺序循环队列的构造

为了充分利用存储空间，消除这种“假溢出”，当队尾指针rear（或队头指针front）到达存储空间的最大值QueueSize的时候，让队尾指针rear（或队头指针front）自动转换为存储空间的最小值0。这样，顺序队列的存储空间就构成一个逻辑上首尾相连的循环队列。

当队尾指针rear达到最大值QueueSize-1时，如果要插入新的元素，队尾指针rear自动变为0；当队头指针front达到最大值QueueSize-1时，如果要删除一个元素，队头指针front自动变为0。可通过取余操作实现循环队列的首位相连。例如，若QueueSize=10，当队尾指针rear=9时，如果要插入一个新的元素，则有rear=（rear+1）%10=0，即实现了逻辑上队列的首尾相连。

2.顺序循环队列的队空和队满

顺序循环队列在队空状态和队满状态时，队头指针front和队尾指针rear同时都指向同一个位置，即front==rear，顺序循环队列的队空状态和队满状态如图3.28所示。队列为空时，有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）少用一个存储空间。队空的判断条件不变，以队尾指针rear加1等于front为队满的判断条件。因此front==rear表示队列为空，front==（rear+1）%QueueSize表示队满。那么，入队的操作语句为：rear=（rear+1）%QueueSize，Q[rear]=x。出队的操作语句为：front=（front+1）%QueueSize。少用一个存储空间时，队满情况如图5.10所示。

注意：顺序循环队列中的入队操作和出队操作，都要取模，以确保操作不出界。循环队列长度即元素个数为（SQ.rear+QueueSize-SQ.front）%QueueSize。

3.顺序循环队列的实现

（1）初始化。

（2）判断队列是否为空。

（3）入队操作。

（4）出队操作。

（5）取队头元素。

（6）清空队列。