文档介绍：第3章堆栈和队列
堆栈
堆栈的应用
队列
优先级队列
本章主要知识点:
堆栈的基本概念,堆栈的用途
顺序堆栈类的设计方法,链式堆栈类的设计方法
队列的基本概念,队列的用途
顺序循环队列的基本实现原理,顺序循环队列的队空和队满判断方法,顺序循环队列类的设计方法
链式堆栈类的设计方法
优先级队列的概念,优先级队列的用途,顺序优先级队列的入队列和出队列操作设计方法
堆栈
堆栈的基本概念
堆栈(栈)是一种特殊的线性表,堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同,其差别是线性表允许在任意位置进行插入和删除操作,而堆栈只允许在固定一端进行插入和删除操作。
栈是在表尾进行插入、删除操作的线性表。
表尾(即 an-1 端)称为栈顶; 表头(即 a0 端)称为栈底
例如: 栈 S= (a0, a1 , a2 , ……….,an-1 )
插入元素到栈顶的操作,称为入栈。
从栈顶删除一个元素的操作,称为出栈。
an-1称为栈顶元素
a0称为栈底元素
强调:插入和删除都只能在表的一端(栈顶)进行!
后进先出表(LIFO)
从输入和输出数据元素的位置关系看,堆栈的功能和一种火车调度装置的功能类同。
注:堆栈可以完成比较复杂的数据元素特定序列的转换任务,但它不能完成任何输入输出序列的转换任务。
例:一个栈的输入序列为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的输出可以实现,每压入一数便立即弹出即可。
例
设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是:
A)a,b,c,d B)c,d,a,b
C)b,c,d,a D)a,c,d,b
A)、D)可以, B)、C)不行。
讨论:有无通用的判别原则?
有!若输入序列是…,Pj…Pk…Pi …(Pj<Pk<Pi) ,一定不存在这样的输出序列…,Pi…Pj…Pk …
答:
即对于输入序列1,2,3,不存在输出序列3,1,2
1数据集合
堆栈的数据集合可以表示为a0,a1,…,an-1,每个数据元素的数据类型可以是任意的类类型。
堆栈抽象数据类型
2操作集合
(1)入栈push(obj):把数据元素obj插入堆栈。
(2)出栈pop():出栈, 删除的数据元素由函数返回。
(3)取栈顶数据元素getTop():取堆栈当前栈顶的数据元素并由函数返回。
(4)非空否notEmpty():若堆栈非空则函数返回true,否则函数返回false。
interface Stack
{
void push(Object obj);
Object pop();
Object getTop();
bool notEmpty();
}
堆栈数据类型的接口定义: