队列ADT,实现与使用接口

列

当从队头移除数据时，例如，移除data0后，队头front指向的数据必须更新为data1，这就有两种方式：一是front保持不动，将所有数据向前移动一格，如图3.30(a)；二是数据保持不动，front增加1，使其指向data1。显然，将所有数据向前移动一格存在大量的数据拷贝，队列中数据越多，数据拷贝操作就越多，效率也就越低，而将front的值加1是非常简单快捷的，因此，一般来讲，都是选择第二种处理方式。

图3.30  队列示意图——出队列

按照方式2，继续将data1、data2、data3出队列，示意图详见图3.31(a)，此时，队列中不存在任何有效数据，rear与front相等，队列为空。

若继续进行数据入队列操作，data4、data5、data6、data7依次进入队列后的示意图详见图3.31(b)，由于队列元素已经存储至最高地址的存储空间，rear已经指向了无效的地址，这种状态时，不能再简单的按照之前的方式，继续向队尾添加数据，否则会因为数组越界而导致程序异常。

图3.31  继续进行出队列、入队列操作

那么，在图3.31(b)所示的情况下，就不能再添加新元素了吗？显然，此时还有一半的空间没有填充数据，一个将空闲空间利用起来的巧妙方法是：当rear或front的值超过最大值后，自动回滚到0。在图3.31(b)，rear已经超过了最大地址，因此，将其回滚到0，详见图3.32(a)。即在逻辑上，将顺序队列视为一个环状的空间，详见图3.32(b)。入队列后，不再是简单的将rear值加1，而是当加1后，判断是否超过了最大地址空间，若超过了，则重新将rear的值设置为0。

图3.32  循环队列

将存储空间视为一个环状后，将更加方便的理解入队列和出队列操作。入队列时，仅需将数据存储值rear指向的空间中，存储完毕后，将rear的值更新为指向下一个存储单元。出队列时，将front指向的空间中的数据取出，并将front的值更新为指向下一个存储单元。

特别地，当front与rear相等时，表示队列为空，无法进行出队列操作，与之对应的，什么时候队列视已满呢？在图3.32(b)的基础上，继续将data8、data9、data10、data11加入队列，使所有空闲单元都存储数据，可以看到加入各个数据后的示意图详见图3.33。

图3.33  data8~data11依次入队列

当data11加入队列后，所有存储单元都存储了数据，此时队列已满，可以看到，当前的front与rear相等，而队列为空时，front与rear也相等。由此可见，只凭front与rear是否相等，无法判断队列是"满"还是"空"。如何解决呢？最简单的方法是增加一个标志，当数据入队列后，出现front与rear相等时，设置该标志位1，以标志当前是"满"状态。而还有一种巧妙的方法，就是实际少用一个存储单元，当front在rear的下一位置时，即图3.33(c)所示状态，就视为队列已满，不再允许新元素加入队列，这种方法的优点是无需增加额外标志，只是将判定队列是否已满的方式修改一下，但其缺点也是很明显的，会浪费一个数据的存储空间。实际上，额外增加标志时，增加的标志也同样需要占用内存空间。

至此，分析了入队列、出队列、判定队列是否为空、判定队列是否为满的实现方法，还剩下最后一个操作没有提及，即确定队列中元素的个数。

而本质上求取元素个数非常简单，只需要将队尾值rear减去队头值front即可，得到的差值即表示队头与队尾之间的数据个数。但需要考虑特殊情况，因为在循环队列中，队尾的值可能小于队头的值，如图3.34(a)、(b)、(c)所示。此时，它们的差值即为负值，如在图3.35(a)中：rear = 1，front = 4，它们的差值为 -3，而实际元素的个数为5。可见，当值为负数时，只需要将其加上存储空间的大小（示例中为8）即可。

上面分析了循环队列的原理，接下来使用程序来实现队列的各个接口，将实现代码全部存放在queue.c文件中。在建立接口时，首先在头文件中定义了抽象队列的类型为：

这里的结构体类型struct queueCDT只有声明，还没有具体的定义。因此无论何种实现方式，都需要先实现struct queueCDT类型的定义。

假定使用的连续空间通过malloc动态分配得到，则在结构体中需要包含一个指向连续空间首地址的指针，以便使用这片内存空间。此外，在上面原理的分析中，需要使用front和rear分别表示队头和队尾的位置，因此队列结构体中需要包含这两个成员，定义队列结构体类型为：

理解了队列各种操作的原理后，则实现起来就较为容易了，详见程序清单 2.34。

程序清单3.71  顺序队列的实现（queue.c）

在getQueueLength()函数的