《数据结构实用教程C语言版》第3章_栈和队列.pptVIP

数据结构实用教程（C语言版） 中国水利水电出版社 3.2.2队列的基本操作 队列的除了在队头进行出队和队尾进行入队外，还有初始化、判空等操作，常用的基本操作有： （1）初始化队列InitQueue(Q)。其作用是构造一个空队列Q。 （2）判断队列空EmptyQueue(Q)。其作用是判断是否是空队列，若队列Q为空，则返回1；否则返回0。 （3）入队EnQueue(Q,x)。其作用是当队列不为满时，将数据元素x插入队列Q的队尾，使其为队列Q的队尾元素。 （4）出队DeQueue(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x，并从队列Q中删除当前队头元素，而其后继元素成为队头元素。 （5）取队头元素GetFront(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x并返回，操作结果只是读取队头元素，队列Q不发生变化。 1. 循环队列的定义 将顺序存储队列的元素的一维数组首尾相接，形成一个环状。如图3-10所示。我们将这种形式表示的队列称为循环队列。循环队列仍然是顺序队列结构，只是逻辑上和前面的顺序队列有所不同。图3-10（a）中队头与队尾指针指向同一位置时为空队，非空队时如图3-10（b）中队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队列的队尾元素位置。 图3-10 循环队列示意图 3.2.4循环队列 假设队列开辟的数组单元数为MAXSIZE，它的数组下标在0～MAXSIZE-1之间，若使队头或队尾增1，可以利用取模运算实现。即 front=(front+1)%MAXSIZE; rear=(rear+1)%MAXSIZE; 【例3.1】图3-10（b）所示的循环队列示意图最大空间为MAXSIZE=8，数组下标为0～7之间，求a5元素入队的位置。 解：入队队尾指针增1 当前队尾指针：rear=7; 入队后队尾指针：rear=(rear+1)%MAXSIZE=0; 3.2.4循环队列 因此，a5元素入队后对应的下标为0。a5元素入队后结果如图3-11所示。 图3-11 图3-10（b）中a5元素入队后循环队列示意图 3.2.4循环队列 2. 循环队列中队空和队满的条件 【例3.2】图3-10（b）所示的循环队列示意图，a5、a6、a7、a8元素依次入队后，其队列如图3-12所示。图3-12所示图中a1、a2、a3、a4、a5、a6、a7、a8元素依次出队后，其队列如图3-13所示。 图3-12 图3-10（b）中a5、a6、a7、a8元素依次入队后循环队列示意图 3.2.4循环队列 2. 循环队列中队空和队满的条件 图3-13 图3-12中a1、a2、a3、a4、a5、a6、a7、a8元素依次出队后循环队列示意图 循环队列解决了顺序队列的“假溢出”现象，但新的问题出现了，队满的条件不再是rear==MAXSIZE-1，而是front==rear和队空的条件相同了。 解决方法：损失一个单元不用，即当循环队列中元素的个数是MAXSIZE-1时就认为队列已满，这样循环队列的队满条件就变成：(rear+1)%MAXSIZE= =front。 队空条件不变仍是：front= =rear。 3.2.4循环队列 2. 循环队列中队空和队满的条件 【例3.3】图3-10（b）所示的循环队列示意图，a5、a6、a7元素依次入队后队满，其队列如图3-14所示。 图3-14 图3-10（b）中a5、a6、a7元素依次入队后队满的循环队列示意图 3.2.4循环队列 3. 循环队列的基本操作实现 （2）判断队列空操作 判断是否是空队列（即Q-front = =Q-rear），若队列Q为空，则返回1；否则返回0，算法描述见算法3.12。 算法3.12 int EmptyQueue (SeqQueue *Q) { if(Q-front==Q-rear) /*队列为空*/ return 1; else return 0; } 3.2.4循环队列 3. 循环队列的基本操作实现（3）入队操作 入队操作的过程如图3-15所示。先判断队列Q如图3-15（a）否已满，若不满再将队中的记录队尾的下标变量rear加1如图3-15（b）所示，最后将入队元素x放进队尾位置上如图3-15（c）所示，算法描述见算法3.13。 3.2.4循环队列 3. 循环队列的基本操作实现 算法3.13 int EnQueue(SeqQueue *Q,ElemType x)