计算机科学与编程导论模块11.ppt

模块十一
堆栈与队列(一)
引入栈和队列
1
2
3
4
栈和队列是操作受限的线性表
栈和队列是操作受限的线性表;
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种常用的数据类型
主要内容
堆栈的概念及其运算 
栈的抽象类定义
栈的定义及其实现
堆栈的应用举例
一堆栈的概念及其运算
堆栈的定义
堆栈的特点
堆栈的示意图
堆栈的有关运算
堆栈的定义
堆栈是一种只允许在表的一端进行插入和删除运算的线性表;
允许进行运算的一端称为栈顶,另一端则称为栈底;
当表中没有元素时,称为空栈;
堆栈的插入运算简称为入栈或进栈,删除运算简称为出栈或退栈。
出栈
进栈
栈的示意图
栈顶
栈底
an
a2
a1
堆栈的特点
出栈
进栈
栈的特点
后进先出
第一个进栈的元素在栈底
最后一个进栈的元素在栈顶
第一个出栈的元素为栈顶元素
最后一个出栈的元素为栈底元素
栈的示意图
栈顶
栈底
an
a2
a1
堆栈的有关运算
进栈运算:在堆栈的顶端插入一个新元素,相当于在线性表最后的元素之后再插入一个新元素;
出栈运算:删除栈顶的元素,在实际应用中,经常要用到栈顶元素。所以,栈顶元素一般应先保存,再删除栈顶结点;
清栈运算:用来将栈清空;
测试栈空:测试当前栈是否为空,栈空时,不能进行出栈运算。下溢;
测试栈满:测试当前栈是否为满,栈满时,不能进行入栈运算。上溢。
二栈的抽象类定义
template<class type> //定义一个抽象的模板堆栈类
class abstack {
public:
bool IsEmpty( ) //判断堆栈是否为空
{ return (height==0)?true:false; }
//进栈函数,将一元素压入栈中
virtual void Push(type&)=0;
//出栈函数,从栈中取一元素
virtual bool Pop(type&)=0;
//清栈函数,用于释放栈所占的内存空间
virtual void Clear( )=0;
protected :
unsigned height; }; //栈高
(1) 抽象栈类中定义了栈高height,可简化操作,例如判断栈空、栈满。height在abstack类中为protected,它的派生类可以访问它。在抽象栈的数据成员中没有栈顶指针,因为顺序栈和链栈的栈顶指针具有不同的数据类型,顺序栈(整型)、链栈(指针型);
(2) 根据栈的常用操作,在abstack类中定义了4个函数,其中3个是纯虚函数,其实现与栈的存储结构有关,因此在派生类中给出其定义。
IsEmpty( ); 判定堆栈是否为空或栈高是否为0;
Push(type &); 将type类型的数据元素插入到栈顶;
Pop(type &); 将栈顶元素弹出并赋给type类型的元素;
Clear( ); 将堆栈清空。
抽象栈类说明: