《数据结构》课程教学资源（PPT课件）第三章 堆栈和队列（3.1 堆栈 3.2 堆栈的应用）

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

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

本章主要知识点：堆栈的基本概念，堆栈的用途顺序堆栈类的设计方法，链式堆栈类的设计方法队列的基本概念，队列的用途顺序循环队列的基本实现原理，顺序循环队列的队空和队满判断方法，顺序循环队列类的设计方法链式堆栈类的设计方法优先级队列的概念，优先级队列的用途，顺序优先级队列的入队列和出队列操作设计方法

本章主要知识点： ● 堆栈的基本概念，堆栈的用途 ● 顺序堆栈类的设计方法，链式堆栈类的设计方法 ● 队列的基本概念，队列的用途 ● 顺序循环队列的基本实现原理，顺序循环队列的队空 和队满判断方法，顺序循环队列类的设计方法 ● 链式堆栈类的设计方法 ● 优先级队列的概念，优先级队列的用途，顺序优先级 队列的入队列和出队列操作设计方法

堆栈3.13.1.1堆栈的基本概念堆栈（栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作

3.1 堆栈 3.1.1 堆栈的基本概念 堆栈（栈）是一种特殊的线性表，堆栈的数 据元素以及数据元素间的逻辑关系和线性表完全 相同，其差别是线性表允许在任意位置进行插入 和删除操作，而堆栈只允许在固定一端进行插入 和删除操作

栈是在表尾进行插入、删除操作的线性表。表尾(即an-1端)称为栈顶；表头(即ao端)称为栈底例如栈 S= (a0, a1 ,a2,..a.)an-i称为栈顶元ao称为栈底元素素强调：插入和删除都只能在表2后进先出表(LIFO)的一端（栈顶）进行！插入元素到栈顶的操作，称为入栈从栈顶删除一个元素的操作，称为出栈

栈 是在表尾进行插入、删除操作的线性表。 表尾(即 an-1 端)称为栈顶 ; 表头(即 a0 端)称为栈底 例如： 栈 S= (a０, a1 , a2 , .,an-1 ) 插入元素到栈顶的操作，称为入栈。 从栈顶删除一个元素的操作，称为出栈。 an-1称为栈顶元 素 a0称为栈底元素 强调：插入和删除都只能在表 的一端（栈顶）进行！ 后进先出表（LIFO）

从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。火车头2火车头1火车头1火车头2(a)(b)(c)注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务

从输入和输出数据元素的位置关系看，堆栈的功能 和一种火车调度装置的功能类同。 (a) (c) (b) 火车头1 火车头1 火车头2 火车头2 注：堆栈可以完成比较复杂的数据元素特定序列的转换 任务，但它不能完成任何输入输出序列的转换任务

例：一个栈的输入序列为1,2.3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：即123;①1入1出，2入2出，3入3出，即132;1入1出，2、3入，3、2出,即231;）1、2入，2出，3入3出，3即213;1、2入，2、1出，3入3出，即321;③1、2、3入，3、2、1出，合计有5种可能性

例：一个栈的输入序列为1,2,3，若在入栈的过程中允 许出栈，则可能得到的出栈序列是什么？ 解：可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入3出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性

例：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可

例：一个栈的输入序列是12345，若在入栈的过 程中允许出栈，则栈的输出序列43512可能实现 吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可

例设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：B)c,d,a,bA)a,b,c,dD) a, c, d,bC) b, c, d,a答：A）、D）可以，B）、C）不行。讨论：有无通用的判别原则？有！若输入序列是...,P...Pk...Pi...(P:<Pk<P)一定不存在这样的输出序列,Pi...P....Pk即对于输入序列1，23，不存在输出序列3，1，2

例 设依次进入一个栈的元素序列为c，a，b，d，则可得到 出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b A）、D）可以，B）、C）不行。 讨论：有无通用的判别原则？ 有！若输入序列是 .,Pj.Pk.Pi .(Pj<Pk<Pi ) ， 一定不存在这样的输出序列 .,Pi.Pj.Pk . 答： 即对于输入序列1，2，3，不存在输出序列3，1，2

3.1.2堆栈抽象数据类型1数据集合堆栈的数据集合可以表示为a0,al....,an-1，每个数据元素的数据类型可以是任意的类类型。2操作集合（1）入栈push(obi)：把数据元素obj插入堆栈。(2)出栈popO：出栈，删除的数据元素由函数返回。（3）取栈顶数据元素getTopO：取堆栈当前栈顶的数据元素并由函数返回。（4）非空否notEmptyO：若堆栈非空则函数返回true否则函数返回false

１数据集合 堆栈的数据集合可以表示为a0,a1,.,an-1，每个数据 元素的数据类型可以是任意的类类型。 3.1.2 堆栈抽象数据类型 ２操作集合 （1）入栈push(obj)：把数据元素obj插入堆栈。 （2）出栈pop()：出栈, 删除的数据元素由函数返回。 （3）取栈顶数据元素getTop()：取堆栈当前栈顶的数 据元素并由函数返回。 （4）非空否notEmpty()：若堆栈非空则函数返回true， 否则函数返回false

堆栈数据类型的接口定义：interface Stackvoid push(Object obi):Object popO;Object getTopO;bool notEmpty(O);人

interface Stack { void push(Object obj); Object pop(); Object getTop(); bool notEmpty(); } 堆栈数据类型的接口定义：