3.4.3 顺序队列
队列有两种存储表示：顺序存储和链式存储。采用顺序存储结构的队列称为顺序队列，采用链式存储结构的队列称为链式队列。
1.顺序队列的表示与实现
顺序队列通常采用一维数组作为存储结构。同时，用两个指针分别指向数组中第一个元素和最后一个元素。其中，指向第一个元素的指针称为队头指针（front），指向最后一个元素的指针称为队尾指针（rear）。队列的表示如图3.22所示。
图3.22 顺序队列
为了方便描述，我们约定：初始化时，队列为空，有front=rear=0，队头指针front和队尾指针rear都指向队列的第一个位置，如图3.23所示。
图3.23 初始化时，顺序队列为空的情况
插入新元素时，队尾指针rear增1，在空队列中插入4个元素a，b，c，d之后，如图3.24所示。
图3.24 顺序队列插入4个元素之后的情况
删除元素时，队头指针front增1。删除2个元素a，b之后，队头和队尾指针状态如图3.25所示。
图3.25 顺序队列删除2个元素之后的情况
顺序队列的类型描述如下：
假设Q是一个队列，若不考虑队满，则入队操作语句为Q.queue[rear++]=x；若不考虑队空，则出队操作语句为x=Q.queue[front++]。
说明：在队列中，队满指的是元素占据了队列中的所有存储空间，没有空闲的存储空间可以插入元素。队空指的是队列中没有一个元素，也称为空队列。
下面是顺序队列的实现算法（以下顺序队列的实现算法在“SeqQueue.h”文件中）。
（1）队列的初始化。
（2）判断队列是否为空。
（3）入队操作。
（4）出队操作。
2.顺序队列的“假溢出”
如果在图3.26所示的队列中插入3个元素j，k和l，然后删除2个元素a，b之后，就会出现如图3.27所示的情况，即队尾指针已经到达数组的末尾，如果继续插入元素m，队尾指针将越出数组的下界而造成“溢出”。从图3.27可以看出，这种“溢出”不是因为存储空间不够，而是经过多次插入和删除操作产生的，将这种“溢出”称为“假溢出”。
图3.26 在插入元素j，k，l和删除元素a，b前
图3.27 在顺序队列中插入j，k，l和删除a，b后的“假溢出”