数据结构 3.2 队列 3.3队列.pptxVIP

算法与数据结构（JAVA语言描述） 模块3 栈和队列 ;学习目的与要求;模块3 栈和队列;3.3.1 队列的概念及基本运算;3．队列的基本运算 （1）initQueue（Q）初始化。构造一个空队列Q。 （2）queueEmpty（Q）判队空。若队列Q为空，则返回true，否则返回false。 （3）queueFull（Q）判队满。若队列Q为满，则返回true，否则返回false。 注意：此操作只适用于队列的顺序存储结构。 （4）enQueue（Q，e）入队。若队列Q非满，则将元素e插入到Q的队尾。 （5）deQueue（Q）出队。若队列Q非空，则删去Q的队头元素。 ;3.3.2 队列的顺序存储结构及其算法实现;如图3.6表示了顺序队列中数据元素和队头、队尾指针之间的对应关系，归纳如下： （1）队头队尾指针在队列初始化时均应置为0。 （2）入队时：将新元素插入rear所指的位置，然后将rear加1。 （3）出队时：删去front所指的元素，然后将front加1。 （4）假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。如图3.6（d）所示，front=2，rear= queueSize时再有元素入队就会发生溢出，但队头前面还有单元是空的。 ;当队列中实际的元素个数远远小于数组空间的规模时，也可能由于尾指针已超越数组空间的上界而不能做入队操作。该现象称为“假上溢”现象。 注意：①当头尾指针相等时，队列为空。 ②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。;2．循环队列 为充分利用数组空间，克服“假上溢”现象，将存放队列元素的数组空间想象为一个首尾相接的圆环，这种形式的顺序队列称为循环队列（Circular Queue）。如图3.7所示。 ;①方法一： if(i+1==queueSize) //i表示front或rear i=0; else i++; ② 方法二：利用模运算 i=(i+1)%queueSize; ;（2）循环队列边界条件处理 如图3.8所示，在循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是空还是满。;解决这个问题的方法至少有三种： ①另设一布尔变量以区别队列的空和满。 ②少用一个元素存??空间。当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指针，所以队满时不会有front=rear。这时队满的条件为(rear+1) % queueSize=front。判队空的条件不变，仍为front=rear。 ③使用一个存储队列中元素个数的变量如count，当count=0时为队空，当count=queueSize时为队满。 以下关于循环队列及其操作算法都基于第3种方法实现。 注意：循环队列中元素的个数为(rear-front+ queueSize)% queueSize; public final int getFront() { return front; } public final void setFront(int front) { this.front = front; } public final int[] getQueue() { return queue; } public final void setQueue(int[] queue) { this.queue = queue; } public final int getRear() { return rear; } public final void setRear(int rear) { this.rear = rear; };①初始化 public void initQueue() { // 将循环队列置空 front = 0; count = 0; rear = 0; } ②判断队列是否为空 public boolean queueEmpty () { // 判断一个循环队列是否为空，若空，返回true，否则返回false return (count == 0); } ③判断队列是否为满 public boolean queueFull() { // 判断一个循环队列是否已满，若满，返回true，否则返回false。 return (count == queue.length); };（4）循环队列的基本运算 ④入队 public void