2.2 和队列的顺序存储结构

2.2.2 顺序队列

　　用顺序表存储的队列称为顺序队列。因为队列的队头和队尾都是活动的，因此，除了队列的数据区外，还必须设置队头、队尾两个指针。
　　1．顺序队列的存储方式
　　一般的队列可采用动态分配空间的方式，类型定义如下：
　　
　　如果设队头指针指向队头元素前面一个位置，队尾指针指向队尾元素（注意：这样的设置是为了某些运算的方便，并不是唯一的方法）。申请一个顺序队列的存储空间：
　　Q.base = (QElemType *)malloc(MAXSIZE*sizeof(QElemType));
　　队列的数据区从Q.base[0]到Q.base[MAXSIZE1]，队头指针为Q.front，队尾指针为Q.rear。入队时执行Q.base[Q.rear++]=e，出队时执行e=Q.base[Q.front++]，置空队列时执行Q.front=Q.rear= -1，队列中元素的个数为m=Q.rearQ.front，队列满的条件是m=MAXSIZE;队列空的条件是m=0。
　　在上述定义的队列中，随着入队、出队的进行，会使整个队列整体向后移动，队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上，此时队列中并未真的“满员”，这种现象称为假溢出。出现假溢出现象是由于“队尾入、队头出”这种受限制的操作所造成的。解决假溢出的方法之一是，将队列定义成动态顺序表，数据区用base[0..MAXSIZE-1]表示，将头尾相接，构成一个循环结构，头尾指针的关系不变。这种结构称为循环队列。
　　另一种方法是牺牲一个元素空间，用“(rear+1)%MAXSIZE==front”表示队满。以下关于循环队列及其操作算法，都基于该方法实现的。循环队列的类型定义如下：
　　
　　2．顺序队列的基本运算
　　顺序队列的操作继承了线性表的基本操作，但又有其特殊性。基本操作有初始化、求队长、入队、出队和判队空等。
　　① 初始化队列。初始化一个队列就是建立队列空间，其算法描述如下：
　　
　　② 求队长。返回队列中元素的个数，其算法描述如下：
　　
　　③ 入队。将一个元素e加入到队尾，其算法描述如下：
　　
　　④ 出队。删除队头元素，并将其值赋给e，其算法描述如下：
　　
　　⑤ 判队空。判断队列是否为空，其算法描述如下：