扫码获取更多资源

●循环队列的定义

在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放队列头到队列尾 的数据元素之外，还需要附设两个指针(front和rear)分别指示队列头元素和队列尾元素的 位置。为了在C语言中描述方便起见，在此约定：初始化建立空队列时，令front = rear=0, 如图3-7(a)所示；每当插入新的队列尾元素时，尾指针增1;每当删除队列头元素时，头指 针增lo因此，在非空队列中，队列头指针front始终指向队列头元素，而队列尾指针rear始 终指向队列尾元素的下一个位置。

当队列有n个数据元素时，顺序存储的队列应该把队列的所有数据元素都依次存储在 数组的前n个单元内。如果把队头元素放在数组中下标为0的一端，则入队操作(在队尾插 入)的时间复杂度仅为0(1),此时的入队操作相当于追加，不需要移动元素，如图3-7(b)所 示；但岀队操作(在队头删除)的时间复杂度为O(n),因为要保证剩下的n-1个元素仍然 存储在数组的前n-1个单元，就必须将所有元素向前移动一个位置，如图3-7(c)所示。如 果把将队列的所有数据元素必须存储在数组的前n个单元这一条件放宽，只要求队列的元 素存储在数组中的连续位置上，则可以得到一种更为有效的存储方法，如图3-7(d)所示。 此时因为没有移动任何元素，入队和出队操作的时间复杂度都是0(1)。图3-7给出了顺序 存储队列中的队列头、尾指针和队列中数据元素之间的关系。

如果采用上述方法，则又遇到一个新的问题。随着入队和岀队操作的进行，整个队列向 数组中下标较大的位置移过去，从而产生了队列的“单向移动性”。当数据元素插入到数组 中下标最大的位置上之后，不可以再继续插入新的队尾元素，否则会因为数组越界而招致程 序代码被破坏；然而此时数组的低端还有空闲空间，这种现象称为“假溢出”，如图3-8所 示，在这种状态下又不宜像顺序栈那样进行存储再分配扩大数组空间，因为队列的实际可用 空间并未占满。解决“假溢出”的一种巧妙方法是将顺序队列臆造为一个环状的空间，如 图3-9所示，即将存储队列的数组看成是头尾相接的循环结构，允许队列直接从数组中下标 最大的位置延续到下标最小的位置，也就是在逻辑上实现循环，而不是在物理上实现循环, 如图3-10所示。利用数学上的取模操作很容易实现这种逻辑上的循环结构。队列的这种 头尾相接的顺序存储结构称为循环队列(Circular Queue)

联系我们：