3.3.2　队列的顺序存储结构及其基本运算的实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。我们先来学习一下队列的顺序存储结构及其基本运算的实现。

顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此除了队列的数据区外还有队头、队尾两个指针。

队头指针：sq－front，队头指针指向队头元素位置；队尾指针：sq－rear，队尾指针指向队尾元素下一个位置（这样的设置是为了某些运算的方便，并不是唯一的方法）。

在不考虑溢出的情况下，入队操作元素入队，队尾指针加1；在不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。入队出队示意图如图3－12所示，设MAXSIZE＝10。

图3－12 队列操作示意图

图3－13 循环队列示意图

从图中可以看到，随着入队出队的进行，整个队列整体向后移动，这样就出现了图3－12（d）中的现象：队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于“队尾入队头出”这种受限制的操作所造成的。解决假溢出的方法之一是将队列的数据区data［0..MAXSIZE－1］看成头尾相接的循环结构，头尾指针的关系不变。

我们将队列的这种头尾相接的顺序存储结构称为循环队列，循环队列的示意图如图3－13所示。

因为是头尾相接的循环结构，入队时的队尾指针加1操作修改为：

出队时的队头指针加1操作修改为：

设MAXSIZE＝10，图3－14为循环队列操作示意图。

从图3－14所示的循环队可以看出，图3－14（a）中具有a5、a6、a7、a8四个元素，此时front＝5，rear＝9；随着a9～a14相继入队，队中具有了10个元素——队满，此时front＝5，rear＝5，如图3－14（b）所示，可见在队满情况下有：front＝＝rear。

若在图3－14（a）情况下，a5～a8相继出队，此时队空，front＝9，rear＝9，如图3－14（c）所示，即在队空情况下也有：front＝＝rear。就是说“队满”和“队空”的条件是相同的了。这显然是必须要解决的一个问题。

图3－14 循环队列操作示意图

方法一：附设一个存储队中元素个数的变量如num，当num＝＝0时队空，当num＝＝MAXSIZE时为队满。

方法二：少用一个元素空间，把图3－14（d）所示的情况视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：（rear＋1）%MAXSIZE＝＝front，也能和空队区别开。

下面的循环队列及操作按第一种方法实现。

算法3.8 循环队列及操作