《数据结构》课程教学资源（PPT课件）第三章 堆栈和队列（3.3 队列 3.4 优先级队列）

第3章 堆栈和队列3.1 堆栈3.2堆栈的应用队列3.3优先级队列3.4

第3章 堆栈和队列 3.1 堆栈 3.2 堆栈的应用 3.3 队列 3.4 优先级队列

3.3 队列3.3.1队列的基本概念队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作

3.3 队列 3.3.1 队列的基本概念 队列也是一种特殊的线性表，队列的数据元 素以及数据元素间的逻辑关系和线性表完全相同， 其差别是线性表允许在任意位置插入和删除，而 队列只允许在其一端进行插入操作在其另一端进 行删除操作

队列在队尾进行插入操作，在队头进行删除操作。先进先出（FIFO）表例如: 队列 Q= (ao , a1 , a2 ....a.2 , an-)队尾队头在队尾插入元素称为入队；在队头删除元素称为出队当队列中没有数据元素时称为空队列

队列 在队尾进行插入操作，在队头进行删除操作。 例如：队列 Q= (a0 , a1 , a2 , .,an-2 , an -1) 在队尾插入元素称为入队；在队头删除元素称为 出队。 当队列中没有数据元素时称为空队列。 队头 队尾 先进先出（ＦＩＦＯ）表

3.3.2队列的抽象数据类型1数据集合队列的数据集合可以表示为a0,al,...,an-l，每个数据元素的数据类型可以是任意的类类型。2操作集合（1）入队列append(obi)：把数据元素obi插入队尾。（2）出队列deleteO：把队头数据元素删除并由函数返回。（3）取队头数据元素getFrontO：取队头数据元素并由函数返回。（4）非空否notEmptyO：非空否。若队列非空，则函数返回true，否则函数返回false

3.3.2 队列的抽象数据类型 1 数据集合 队列的数据集合可以表示为a0,a1,.,an-1，每个数据 元素的数据类型可以是任意的类类型。 2 操作集合 （1）入队列append(obj)：把数据元素obj插入队尾。 （2）出队列delete()：把队头数据元素删除并由函数返回。 （3）取队头数据元素getFront()：取队头数据元素并由函 数返回。 （4）非空否notEmpty()：非空否。若队列非空，则函数返 回true，否则函数返回false

队列抽象数据类型的接口定义如下：interface Queuelvoid append(Object obj);Object deleteO;Object getFrontO;bool notEmptyO;

队列抽象数据类型的接口定义如下： interface Queue{ void append(Object obj); Object delete(); Object getFront(); bool notEmpty(); }

3.3.3顺序队列1顺序队列的存储结构下图是一个有6个存储空间的顺序队列的示意图，图中front指示队头，rear指示队尾。555rear=5E44443D3rear=3rear=322cCcfront=front=2B111front0front=0A0= 0rear(a)(b)(c)(d)

1 顺序队列的存储结构 下图是一个有6个存储空间的顺序队列的示意图，图中 front指示队头，rear指示队尾。 4 3 2 1 = 0 5 front rear (a) C B A 4 3 2 1 0 5 front= rear= (b) C 4 3 2 1 0 5 front= rear= (c) E D C 4 3 2 1 0 5 front= rear= (d) 3.3.3 顺序队列

2顺序队列的“假溢出”问题顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称作假溢出6rear=5rear=5F4EE43D3D2front=c2front=C100

2 顺序队列的“假溢出”问题 E D C 4 3 2 1 0 5 F front= rear= 6 E D C 4 3 2 1 0 5 front= rear= 顺序队列因多次入队列和出队列操作后出现的有存储空间但 不能进行入队列操作的溢出称作假溢出

3顺序循环队列的基本原理假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的。因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到maxSize-1后，再加1就自动到o。这样，就不会出现顺序队列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题

3 顺序循环队列的基本原理 假溢出是由于队尾rear的值和队头front的值不能由 所定义数组下界值自动转为数组上界值而产生的。因 此，解决的方法是把顺序队列所使用的存储空间构造 成一个逻辑上首尾相连的循环队列。 当rear和front达到maxSize-1后，再加1就自动到0。 这样，就不会出现顺序队列数组的头部已空出许多存 储空间，但队尾却因数组下标越界而引起溢出的假溢 出问题

例：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置？J2J3J8J9rearJ7J1J4J6J5front=1J5front=5front-5rear-0rear=0解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后，front=(1+4)%6=5；再插入4个元素后，rear=(0+4)%6=4

例： 一循环队列如下图所示，若先删除4个元素，接着再 插入4个元素，请问队头和队尾指针分别指向哪个位置? J2 J3 J1 J4 front=1 J5 rear=0 解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。 删除4个元素后，front= (1+4)%6 =5； 再插入4个元素后，rear=(0+4)%6=4 front=5 J6 J5 J7 J8 J9 rear=4 rear=0 front=5

4顺序循环队列的队空和队满判断问题数据元素入队列front=ofront=oA5AA4040rear=l3312B2front=orear=0rear=2FE5A4031D2B队列满状态front==rearC

4 顺序循环队列的队空和队满判断问题 1 5 4 0 3 2 front=0 rear=1 A 1 5 4 0 3 2 front=0 rear=2 A B 1 5 4 0 3 2 E D F A B C rear=0 front=0 队列满状态front==rear 数据元素入队列