第三章 堆栈和队列

,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 堆栈和队列,3.1,堆栈,3.2,堆栈的应用,3.3,队列,3.4,优先级队列,本章主要知识点：,堆栈的基本概念，堆栈的用途,顺序堆栈类的设计方法，链式堆栈类的设计方法,队列的基本概念，队列的用途,顺序循环队列的基本实现原理，顺序循环队列的队空和队满判断方法，顺序循环队列类的设计方法,链式堆栈类的设计方法,优先级队列的概念，优先级队列的用途，顺序优先级 队列的入队列和出队列操作设计方法,3.1,堆栈,-,基本概念,堆栈,是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。,堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。,从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。,3.1,堆栈,-,基本概念,a,1,a,2,a,3,入栈,出栈,栈底,栈顶,插入：入栈、进栈、压栈,删除：出栈、弹栈,栈顶,栈顶,栈的示意图,3.1,堆栈,-,基本概念,栈的操作特性：,后进先出,a,1,a,2,a,3,入栈,出栈,栈底,栈顶,插入：入栈、进栈、压栈,删除：出栈、弹栈,栈顶,栈的示意图,3.1,堆栈,-,基本概念,数据集合,堆栈的数据集合可以表示为,a0,a1,an-1,，每个数据元素的数据类型可以是任意的类类型。,操作集合,（,1,）入栈,push(obj,),：把数据元素,obj,插入堆栈。,（,2,）出栈,pop(),：出栈,删除的数据元素由函数返回。,（,3,）取栈顶数据元素,getTop,(),：取堆栈当前栈顶的数据元素并由函数返回。,（,4,）非空否,notEmpty,(),：若堆栈非空则函数返回,true,，否则函数返回,false,。,3.1,堆栈,-,抽象数据类型,顺序存储结构的堆栈称作,顺序堆栈,。,3.1,堆栈,-,顺序堆栈,链式存储结构的堆栈称作,链式堆栈,。,1,链式堆栈的存储结构,和单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域,element,，另一个是存放指向下一个结点的对象引用（即指针）域,next,。,堆栈有两端，插入数据元素和删除数据元素的一端为栈顶，另一端为栈底。链式堆栈都设计成把靠近堆栈头,head,的一端定义为栈顶。,3.1,堆栈,-,链式堆栈,2,链式堆栈的示意图,3.1,堆栈,-,链式堆栈,堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。,3.2.1,括号匹配问题,3.2.2,表达式计算问题,3.2,堆栈的应用,3.3,队列,-,基本概念,队列,（简称作队）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。,队列中允许进行插入操作的一端称为,队尾,，允许进行删除操作的一端称为,队头,。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。,3.3,队列,-,逻辑结构,队列的操作特性：,先进先出,a,1,a,2,a,3,入队,队尾,队头,出队,队头,3.3,队列,-,抽象数据类型,1,数据集合,队列的数据集合可以表示为,a,0,a,1,a,n-1,，每个数据元素的数据类型可以是任意的类类型。,2,操作集合,（,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,队列,-,抽象数据类型,1,顺序队列的存储结构,front,指示队头，,rear,指示队尾。,3.3,队列,-,顺序队列,2,顺序队列的“假溢出”问题,顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称作,假溢出,。,3.3,队列,-,顺序队列,顺序循环队列的基本原理,假溢出是由于队尾,rear,的值和队头,front,的值不能由所定义数组下界值自动转为数组上界值而产生的。因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。,当,rear,和,front,达到,maxSize-1,后，再加,1,就自动到,0,。这样，就不会出现顺序队列数组的头部已空出许多存储空间，但队尾却因数组下标越界而引起溢出的假溢出问题。,3.3,队列,-,顺序队列,4,顺序循环队列的队空和队满判断问题,顺序循环队列的队列满和队列空状态,（,a,）初始化状态；（,b,）队列满状态；（,c,）队列空状态,3.3,队列,-,顺序队列,解决顺序循环队列的队列满和队列空状态判断问题通常有三种方法：,（,1,）,少用一个存储空间,当少用一个存储空间时，以队尾,rear,加,1,等于队头,front,为队列满的判断条件，即队列满的判断条件：,(rear + 1) %,maxSize,= front,队列空的判断条件仍然为：,rear = = front,3.3,队列,-,顺序队列,（,2,）,设置一个标志位,添加一个标志位。设标志位为,tag,，初始时置,tag=0,；每当入队列操作成功就置,tag=1,；每当出队列操作成功就置,tag=0,。则队列空的判断条件为：,rear = front & tag=0,队列满的判断条件为：,rear = = front & tag= =1,3.3,队列,-,顺序队列,（,3,）,设置一个计数器,添加一个计数器。设计数器为,count,，初始时置,count=0,；每当入队列操作成功就使,count,加,1,；每当出队列操作成功就使,count,减,1,。这样，该计数器不仅具有计数功能，而且还具有像标志位一样的标志作用，则此时队列空的判断条件为：,count = 0,队列满的判断条件为：,count 0 & rear = front,顺序循环队列类,3.3,队列,-,顺序队列,链式存储结构的队列称作,链式队列,。,1,链式队列的存储结构,3.3,队列,-,链式队列,链式,队列类,操作系统中的各种数据缓冲区的先进先出管理,应用系统中的各种服务请求的排队管理,例子： 编写判断一个字符序列是否是回文的函数，并设计一个主函数进行测试。,3.3,队列,应用,实现,3.4,优先级队列,优先级队列,是带有优先级的队列。,用顺序存储结构实现的优先级队列称作,顺序优先级队列,。,用链式存储结构存储的优先级队列称作,链式优先级队列,。,1,顺序优先级队列类,顺序优先级队列和顺序循环队列相比主要有两点不同：,（,1,）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。,（,2,）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为,int,类型的数值，并规定数值越小优先级越高。,Element,顺序优先级队列类,2,优先级队列的应用,操作系统的进程管理软件中就使用了优先级队列。操作系统中使用一个优先级队列来管理进程。当优先级队列中有若干个进程排队等待系统响应，并且,CPU,资源空闲时，进程管理系统就可从优先级队列中找出优先级最高的进程首先出队列，从而既达到了当系统繁忙时，所有进程都排队等待，又达到了实时性要求高的进程先被服务的双重要求。,模仿操作系统的进程管理问题的程序,3.4,优先级队列,