数据结构 第3章-堆栈和队列ppt课件.ppt

《数据结构 第3章-堆栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、引言堆栈和队列也是最常见的数据结构，在算法设计中经常使用。堆栈和队列在逻辑上同线性表一样，都是线性结构，差别在于：线性表可以在表的任意位置插入和删除元素，而堆栈和队列只能在表的端点插入和删除元素。第3章堆栈和队列数据结构DATASTRUCTURE内容提要1.定义堆栈与队列抽象数据类型2.讨论堆栈与队列的顺序表示方法3.讨论堆栈与队列的链接表示方法4.以表达式计算为例讨论堆栈的应用3.1堆栈a0a1…ai…an-1入栈出栈bottomtop图3-1栈的示意图栈的示意图S=(a0,a1,…,an-1)课堂提要第3

2、章堆栈和队列3.1堆栈3.2队列3.3表达式的计算3.1.1堆栈抽象数据类型堆栈（简称栈）是限定插入和删除操作都在表的一端进行的线性表。若栈中无元素，则为空栈。允许插入和删除元素的一端称为栈顶，另一端称为栈底。S=(a0,a1,…,an-1)1.堆栈的定义课堂提要第3章堆栈和队列3.1堆栈3.1.1栈抽象数据类型3.1.2栈的顺序表示3.1.3栈的链接表示3.2队列3.3表达式的计算若给定栈S=(a0,a1,…,an-1)，则称a0是栈底元素，an-1是栈顶元素。若元素a0,…,an-1依次进栈时，则出栈的顺

3、序与进栈相反，即元素an-1必定最先出栈，然后an-2才能出栈。因此，栈是后进先出(LastInFirstOut——LIFO)的线性数据结构。a0a1…ai…an-1入栈出栈bottomtop图3-1栈的示意图2.栈抽象数据类型ADTStack{Data:零个或多个元素的线性序列（a0,a1,...,an-1),其最大允许长度为ＭaxStackSize。对于它插入和删除运算都限制在同一端进行，并遵循LIFO原则。Operations:Create()：建立一个空栈。Destroy()：撤消一个栈。IsEmpt

4、y()：若栈空，则返回true;否则返回false。IsFull()：若栈满，则返回true;否则返回false。Top(x)：返回栈顶元素。若操作成功，则返回true;否则返回false。Push(x)：在栈顶插入元素x。Pop()：　从栈中删除栈顶元素。Clear():清除堆栈中全部元素。};3.栈的C++模板抽象类程序3-1栈的C++类templateclassStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()cons

5、t=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1.2栈的顺序表示1.栈的顺序表示法an-1a1a0topn-110栈s图3-2顺序栈maxTop………课堂提要第3章堆栈和队列3.1堆栈3.1.1栈抽象数据类型3.1.2栈的顺序表示3.1.3栈的链接表示3.2队列3.3表达式的计算2.顺序栈类templateclassSeqStack:publicS

6、tack{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//总是指向栈顶元素intmaxTop;T*s;}an-1a1a0topn-110栈s图3-2顺序

7、栈maxTop………3.动态一维数组描述顺序栈类templateclassSeqStack:publicStack{public:……private:intmaxTop;inttop;T*s;}an-1a1a0topn-110栈s图3-2顺序栈maxTop………构造函数templateSeqStack::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析构函数SeqStack::~SeqStack

8、(intMaxSize){delete[]s;}an-1a1a0topn-110栈s图3-2顺序栈maxTop………4.在顺序存储表示下实现栈上定义的操作（1）取栈顶元素templateboolSeqStack::Top(T&x)const{if(IsEmpty()){cout<<"Empty"<