3.1.5　顺序队列

1. 类型定义

2. 队的状态

图3-2 顺序队列的状态变化

(1) 规定

队头指针front总是指向队列中第1个元素的前一个位置；队尾指针rear总是指向队列中最后一个元素。

(2) 队空

参见图3-2(a)和图3-2(c)。判断条件：q-＞rear==q-＞front

(3) 入队

操作：q-＞rear++;q-＞data[q-＞rear]=x;参见图3-2(b)。

(4) 出队

操作：q-＞front++;出队元素x=q-＞data[q-＞front],参见图3-2(c)。

(5) 顺序队队满

判断条件：(q-＞rear-q-＞front)==MaxSize

(6) 假溢出

参见图3-2(d)，这时队头有空闲存储单元，但由于q-＞rear==MaxSize，下一个元素a₅不能执行正常的入队操作，因为若执行q-＞rear++；数组将产生溢出。

(7) 解决假溢出的方法

①由于假溢出使a₅不能正常入队，可以考虑将a₄向队头移动一个位置。

②在a₁，a₂，a₃出队过程中，队头元素的空间已空闲，可以考虑当有元素出队时，便将其余元素向队头移动一个位置。

③上述两种方法都涉及了元素的移动，次序较低。实际应用中更多地是采用循环队列。