第3章栈和队列 3.3顺序队列《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第三章：栈和队列 3.3.2 顺序队列 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针来分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为－1。入队时尾指针加１，然后将新元素插入尾指针所指的位置。出队时，头指针加１，删去所指的元素。 由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素的前一个位置，而尾指针始终指向队尾元素。 队列的顺序存储结构定义及变量说明如下： #define MAXSIZE 100 typedef struct { datatype data[MAXSIZE]; int front; int rear; }sequeue; sequeue * sq; 　 ０ １ ２ ３ 0 1 2 3 　 front rear a b c Front rear (a) 队列初始为空　　　　 (b) A,B,C入队 　 ０　 １　 ２　 ３　　　 ０　１　 ２　 ３ b c front rear front rear (c) a出队 (d) b,c出队，队为空 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 顺序队列各种状况下头尾指针情况： 队空：sq->front= sq-> rear 队满： sq-> rear=maxsize（假溢出） 求队长： sq-> rear－ sq-> front 入队：先将队尾指针加一，再按 sq-> rear 指示位置加入新元素。 即 : sq-> rear ++; sq->data[sq->rear]=x; 出队：将队头指针sq-> front加一。 即： sq-> front ++; 和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 显然，因为循环队列元素的空间可以被充分利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 0 1 2 3 4 5 sq-> rear sq-> front J4 J5 J6 0 1 2 3 4 5 sq-> rear sq-> front J9 J8 J7 J4 J5 J6 0 1 2 3 4 5 sq-> rear sq->front 初始状态 J4,J5,J6出队 J7,J8,J9入队 队空： sq-> front== sq-> rear 队满： sq-> front== sq-> rear 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空： sq-> front== sq-> rear 队满：(sq-> rear+1)%MAXSIZE == sq-> front 如上图所示：入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过 sq->front=