《数据结构》课程授课教案（讲稿）第三章 堆栈和队列 第二节 队列

课程名称：数据结构第_6周，第_6讲次摘要第三章堆栈和队列授课题目（章、节）第二节队列【目的要求】通过本讲课程的学习，理解队列的逻辑结构定义及在两种存储结构上如何实现队列的基本运算。要求在掌握队列的特点的基础上，懂得在什么样的情况下能够使用队列，另外了解优先级队列。【重点】顺序循环队列的设计。【难点】理解顺序队列假溢出的产生原因以及解决方法，掌握判断顺序循环队列空满的方法。内容【本讲课程的引入】堆栈是一种具有后进先出特点的受限线性表，这一次课我们要学习另外一种受限的线性表一一队列。【本讲课程的内容】3.3队列3.3.1队列的基本概念队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。队列是仅在队尾进行插入操作，在队头进行删除操作的线性表。它是一种先进先出（FIFO）的线性表。在队尾插入元素称为入队：在队头删除元素称为出队。当队列中没有数据元素时称为空队列。3.3.2队列的抽象数据类型数据集合队列的数据集合可以表示为ao,al，，an-1，每个数据元素的数据类型可以是任意的类类型。操作集合（1）入队列append（obj）：把数据元素obj插入队尾。（2）出队列delete（)：把队头数据元素删除并由函数返回。（3）取队头数据元素getFront（)：取队头数据元素并由函数返回。（4）非空否notEmptyO：非空否。若队列非空，则函数返回true，否则函数返回false。队列抽象数据类型的Java接口定义如下：public interface Queuefpublicvoidappend(Objectobj)throwsException;publicObjectdelete()throwsException;public Object getFront(throws Exception;public boolean notEmptyO:3.3.3顺序队列1顺序队列的存储结构下图是一个有6个存储空间的顺序队列的动态示意图，图中front指示队头，rear指

课程名称：数据结构 第 6 周，第 6 讲次 摘 要 授课题目（章、节） 第三章 堆栈和队列 第二节 队列 【目的要求】通过本讲课程的学习，理解队列的逻辑结构定义及在两种存储结构上如何实现队列的基本运算。 要求在掌握队列的特点的基础上，懂得在什么样的情况下能够使用队列，另外了解优先级队列。 【重 点】顺序循环队列的设计。 【难 点】理解顺序队列假溢出的产生原因以及解决方法，掌握判断顺序循环队列空满的方法。 内 容 【本讲课程的引入】堆栈是一种具有后进先出特点的受限线性表，这一次课我们要学习另 外一种受限的线性表——队列。 【本讲课程的内容】 3.3 队列 3.3.1 队列的基本概念 队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完 全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操 作在其另一端进行删除操作。 队列是仅在队尾进行插入操作，在队头进行删除操作的线性表。它是一种先进先出（Ｆ ＩＦＯ）的线性表。 在队尾插入元素称为入队；在队头删除元素称为出队。 当队列中没有数据元素时称为空队列。 3.3.2 队列的抽象数据类型 数据集合 队列的数据集合可以表示为 a0,a1,.,an-1，每个数据元素的数据类型可以是任意的 类类型。 操作集合 （1）入队列 append(obj)：把数据元素 obj 插入队尾。 （2）出队列 delete()：把队头数据元素删除并由函数返回。 （3）取队头数据元素 getFront()：取队头数据元素并由函数返回。 （4）非空否 notEmpty()：非空否。若队列非空，则函数返回 true，否则函数返回 false。 队列抽象数据类型的 Java 接口定义如下： public interface Queue{ public void append(Object obj) throws Exception; public Object delete() throws Exception; public Object getFront() throws Exception; public boolean notEmpty(); } 3.3.3 顺序队列 1 顺序队列的存储结构 下图是一个有 6 个存储空间的顺序队列的动态示意图，图中 front 指示队头，rear 指

示队尾。下图分别表示了空队列、数据元素ABC分别入队列、AB出队列、DE入队列的情况。rear= 54Y3rear= 3rear= 33Dfront= 2front= 22ncL1-611front =0front=040rear(a)(b)(c)(a)2顺序队列的“假溢出”问题设一个顺序队列的最大存储空间为6，经入队列ABC出队列AB，入队列DE操作后，此时若再要进行入队列FG操作，则当进行数据元素G入队列操作时，顺序队列将因越出数组下界而“溢出”，从下图可以看出，此时的溢出是因为队尾rear的值超出了顺序队列定义的maxSize=6的数组下界而引起的，但此时队列中还有2个数据元素空间可供存储，因此这时的溢出并不是由于数组空间不够而产生的溢出。顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称作假溢出。rear= 65P43DCfront= 21o3顺序循环队列的基本原理假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的。因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到maxSize-1后，再加1就自动到0。这样，就不会出现顺序队列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题。4顺序循环队列的队空和队满判断问题解决顺序循环队列的队列满和队列空状态判断问题通常有三种方法：（1）少用一个存储空间当少用一个存储空间时，以队尾rear加1等于队头front为队列满的判断条件，即队列满的判断条件此时为：(rear+1)%maxSize==front队列空的判断条件仍然为：

示队尾。 下图分别表示了空队列、数据元素 ABC 分别入队列、AB 出队列、DE 入队列的情 况。 2 顺序队列的“假溢出”问题 设一个顺序队列的最大存储空间为 6，经入队列 ABC 出队列 AB，入队列 DE 操作后，此 时若再要进行入队列 FG 操作，则当进行数据元素 G 入队列操作时，顺序队列将因越出数组 下界而“溢出”，从下图可以看出，此时的溢出是因为队尾 rear 的值超出了顺序队列定义 的 maxSize=6 的数组下界而引起的，但此时队列中还有 2 个数据元素空间可供存储，因此 这时的溢出并不是由于数组空间不够而产生的溢出。 顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的 溢出称作假溢出。 3 顺序循环队列的基本原理 假溢出是由于队尾 rear 的值和队头 front 的值不能由所定义数组下界值自动转为数 组上界值而产生的。因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上 首尾相连的循环队列。 当 rear 和 front 达到 maxSize-1 后，再加 1 就自动到 0。这样，就不会出现顺序队 列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题。 4 顺序循环队列的队空和队满判断问题 解决顺序循环队列的队列满和队列空状态判断问题通常有三种方法： （1）少用一个存储空间 当少用一个存储空间时，以队尾 rear 加 1 等于队头 front 为队列满的判断条件， 即队列满的判断条件此时为： (rear + 1) % maxSize == front 队列空的判断条件仍然为： 4 3 2 1 = 0 5 front rear C B A 4 3 2 1 0 5 front= rear= C 4 3 2 1 0 5 front= rear= E D C 4 3 2 1 0 5 front= rear= (a) (b) (c) (d) E D C 4 3 2 1 0 5 F front= rear= 6

rear == front（2）设置一个标志位添加一个标志位。设标志位为tag，初始时置tag=0；每当入队列操作成功就置tag=1：每当出队列操作成功就置tag=0。则队列空的判断条件为：rear ==front &&tag==0队列满的判断条件为：rear ==front && tag==1（3）设置一个计数器添加一个计数器。设计数器为count，初始时置count=O：每当入队列操作成功就使count加1；每当出队列操作成功就使count减1。这样，该计数器不仅具有计数功能，而且还具有像标志位一样的标志作用，则此时队列空的判断条件为：count == o队列满的判断条件为：count>o&&rear==front3.3.4顺序循环队列类publicclassSeqQueueimplementsQueuefinal int defaultSize=10int front,int rear,int count;int maxSize,Object[] data;publicSeqQueueOinitiate(defaultSize),3public SeqQueue(int sz)initiate(sz);private void initiate(int sz)maxSize= sz,front=rear = 0;count =0,data =new Object[sz];1public void append(Object obi)throws Exceptionif(count>0 && front == rear)(thrownewException("队列已满！"）；7data[rear] = obj;rear = (rear + 1)% maxSize;count ++;1

rear = = front （2）设置一个标志位 添加一个标志位。设标志位为 tag，初始时置 tag=0；每当入队列操作成功就置 tag=1； 每当出队列操作成功就置 tag=0。则队列空的判断条件为： rear == front && tag==0 队列满的判断条件为： rear = = front && tag= =1 （3）设置一个计数器 添加一个计数器。设计数器为 count，初始时置 count=0；每当入队列操作成功就使 count 加 1；每当出队列操作成功就使 count 减 1。这样，该计数器不仅具有计数功能，而 且还具有像标志位一样的标志作用，则此时队列空的判断条件为： count == 0 队列满的判断条件为： count > 0 && rear == front 3.3.4 顺序循环队列类 public class SeqQueue implements Queue{ final int defaultSize = 10; int front; int rear; int count; int maxSize; Object[] data; public SeqQueue(){ initiate(defaultSize); } public SeqQueue(int sz){ initiate(sz); } private void initiate(int sz){ maxSize = sz; front = rear = 0; count = 0; data = new Object[sz]; } public void append(Object obj) throws Exception{ if(count > 0 && front = = rear){ throw new Exception("队列已满！"); } data[rear] = obj; rear = (rear + 1) % maxSize; count ++; }

public ObjectdeleteOthrowsExceptiontif(count== 0)thrownewException("队列已空！");1Object temp = data[front];front=(front+1) %maxSize;count --,return temp,public Object getFront(O) throws Exceptionif(count== 0)thrownewException("队列己空！");return data[front];publicbooleannotEmpty()return count != 0;33.3.5链式队列链式存储结构的队列称作链式队列。1链式队列的存储结构frontTean-2an-iAaoa★2链式队列类设计public class LinQueue implements QueuelNode front;Node rear;int count;publicLinQueueOinitiateO;private void initiateOfront=rear= null;count = O,1public Object getFront()throws Exceptiontif(count=0)thrownewException("队列己空！");

public Object delete() throws Exception{ if(count == 0){ throw new Exception("队列已空！"); } Object temp = data[front]; front = (front + 1) % maxSize; count -; return temp; } public Object getFront() throws Exception{ if(count == 0){ throw new Exception("队列已空！"); } return data[front]; } public boolean notEmpty(){ return count != 0; } } 3.3.5 链式队列 链式存储结构的队列称作链式队列。 1 链式队列的存储结构 2 链式队列类设计 public class LinQueue implements Queue{ Node front; Node rear; int count; public LinQueue(){ initiate(); } private void initiate(){ front = rear = null; count = 0; } public Object getFront() throws Exception{ if(count == 0) throw new Exception("队列已空！"); a0 . a1 an−2 an−1 ∧ front rear

returnfront.getElementO);1public boolean notEmpty(return count != O;1public void append(Object obi)NodenewNode=newNode(obj,null),if(rear I= null)rear.next = newNode;rear= newNode;if(front == null)front = newNode;count ++;1public Object delete()throws Exception)if(count==0)thrownewException("队列己空！");Nodetemp=front;front= front.next;count --,return temp.getElement),:33.4优先级队列优先级队列是带有优先级的队列。用顺序存储结构实现的优先级队列称作顺序优先级队列。用链式存储结构存储的优先级队列称作链式优先级队列。顺序优先级队列和顺序循环队列相比主要有两点不同：（1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。因此顺序优先级队列出队列操作的实现方法是首先在遍历队列数据元素的基础上找出优先级最高的数据元素，然后依次把从该数据元素后一个的元素直到队尾的元素前移一个位置（和顺序表删除操作的方法类同）。由于每次出队列操作都把队列中从优先级最高元素后一个的元素至队尾的所有元素前移，所以顺序优先级队列不会出现顺序队列那样的假溢出问题。因此顺序优先级队列不用设计成循环结构。（2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。3.4.1顺序优先级队列类publicclassSeqPQueuestatic final int defaultSize= 10;int front,int rear,int count;int maxSize;Element[] data

return front.getElement(); } public boolean notEmpty(){ return count != 0; } public void append(Object obj){ Node newNode = new Node(obj,null); if(rear != null) rear.next = newNode; rear = newNode; if(front == null) front = newNode; count ++; } public Object delete() throws Exception{ if(count == 0) throw new Exception("队列已空！"); Node temp = front; front = front.next; count -; return temp.getElement(); } } 3.4 优先级队列 优先级队列是带有优先级的队列。 用顺序存储结构实现的优先级队列称作顺序优先级队列。 用链式存储结构存储的优先级队列称作链式优先级队列。 顺序优先级队列和顺序循环队列相比主要有两点不同： （1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优 先级最高的数据元素出队列。 因此顺序优先级队列出队列操作的实现方法是首先在遍历队列数据元素的基础上找出 优先级最高的数据元素，然后依次把从该数据元素后一个的元素直到队尾的元素前移一个 位置（和顺序表删除操作的方法类同）。由于每次出队列操作都把队列中从优先级最高元素 后一个的元素至队尾的所有元素前移，所以顺序优先级队列不会出现顺序队列那样的假溢 出问题。因此顺序优先级队列不用设计成循环结构。 （2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素， 另一部分是优先级。通常设计优先级为 int 类型的数值，并规定数值越小优先级越高。 3.4.1 顺序优先级队列类 public class SeqPQueue{ static final int defaultSize = 10; int front; int rear; int count; int maxSize; Element[] data;

public SeqPQueueOtthis.initiate(defaultSize);1public SeqPQueue(int sz)this.initiate(sz);private void initiate(int sz)maxSize = sz,front=rear = 0;count = 0;data =new Element[sz];public voidappend(Object obi)throws Exceptiontif(count>=maxSize)thrownewException("队列已满！"）data[rear] = (Element)obj;rear = rear + 1;count ++;public Element delete()throws Exception(if(count == 0)thrownewException("队列已空！");子Element min = data[0];int minIndex = O;for(int i= 1;i<count; i++)if(data[i].getPriorityO<min.getPriorityO)min = data[i];minIndex =i;3for (int i=minlndex + 1; i<count; i++)data[i- 1] = data[i];-rear= rear - 1;count --,return min,publicObjectgetFront(）throwsException//取队头数据元素if(count== 0)thrownewException("队列己空！");享Elementmin= data[0]

public SeqPQueue(){ this.initiate(defaultSize); } public SeqPQueue(int sz){ this.initiate(sz); } private void initiate(int sz){ maxSize = sz; front = rear = 0; count = 0; data = new Element[sz]; } public void append(Object obj) throws Exception{ if(count >= maxSize){ throw new Exception("队列已满！"); } data[rear] = (Element)obj; rear = rear + 1; count ++; } public Element delete() throws Exception{ if(count == 0){ throw new Exception("队列已空！"); } Element min = data[0]; int minIndex = 0; for(int i = 1; i < count; i ++){ if(data[i].getPriority() < min.getPriority()){ min = data[i]; minIndex = i; } } for (int i = minIndex + 1; i < count; i++){ data[i - 1] = data[i]; } rear = rear - 1; count -; return min; } public Object getFront() throws Exception{ //取队头数据元素 if(count == 0){ throw new Exception("队列已空！"); } Element min = data[0];

int minlndex = O;for(inti=O:i<count:i++)if(data[i].getPriorityO<min.getPriorityO)(min = data[i];minIndex = i;31returnmin,3.4.2优先级队列的应用操作系统中的进程管理软件中就使用了优先级队列。操作系统中使用一个优先级队列来管理进程。当优先级队列中有若干个进程排队等待系统响应，并且CPU资源空闲时，进程管理系统就可从优先级队列中找出优先级最高的进程首先出队列，从而既达到了当系统繁忙时，所有进程都排队等待，又达到了实时性要求高的进程先被服务的双重要求。【本讲课程的小结】队列是一种受限线性表，它只能在固定的一端进行插入，固定的一端进行删除，这就使得队列具有先进先出的特点。由于顺序队列存在假溢出问题，因此队列的顺序存储通常设计成顺序循环队列，而如何判断循环队列的空满是我们要注意的一个问题。这一章中我们学习的队列和堆栈是在实际应用中经常用到的数据结构，所以对于它们的结构特点一定要深入理解。【本讲课程的作业】编写判断一个字符序列是否是回文的函数，要求同时使用堆栈和队列

int minIndex = 0; for(int i = 0; i < count; i ++){ if(data[i].getPriority() < min.getPriority()){ min = data[i]; minIndex = i; } } return min; } 3.4.2 优先级队列的应用 操作系统中的进程管理软件中就使用了优先级队列。操作系统中使用一个优先级队列来 管理进程。当优先级队列中有若干个进程排队等待系统响应，并且 CPU 资源空闲时，进程 管理系统就可从优先级队列中找出优先级最高的进程首先出队列，从而既达到了当系统繁 忙时，所有进程都排队等待，又达到了实时性要求高的进程先被服务的双重要求。 【本讲课程的小结】队列是一种受限线性表，它只能在固定的一端进行插入，固定的一端 进行删除，这就使得队列具有先进先出的特点。由于顺序队列存在假溢出问题，因此队列 的顺序存储通常设计成顺序循环队列，而如何判断循环队列的空满是我们要注意的一个问 题。这一章中我们学习的队列和堆栈是在实际应用中经常用到的数据结构，所以对于它们 的结构特点一定要深入理解。 【本讲课程的作业】 编写判断一个字符序列是否是回文的函数，要求同时使用堆栈和队列