(最新)数据结构与算法课件c语言表述chapter5栈-栈的应用（1）

《(最新)数据结构与算法课件c语言表述chapter5栈-栈的应用（1）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法2010年秋季授课教师：张剑波授课班级：111091-2、114091-2班1Chapter5栈（Stack）2本章教学内容5.1栈的结构特点5.2栈的抽象数据类型5.3栈的公式化描述（顺序栈）5.4栈的链表描述（链式栈）5.5栈的应用35.1栈（Stack）的结构特点【定义】栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为【栈顶（top）】；另一端为固定的一端，称为【栈底（bottom）】。特性：后进先出（L

2、astInFirstOut）。栈简称为为LIFO表。topanan-1…a2a1bottom进栈出栈42002年中地大考研题：【选择题】设对一个适当大小的栈，若输入序列为ABCDEF，则不可能的出栈序列是：A、ABCDEFB、DCEBFAC、CBEADFD、BEDFCAC2000年南开大学考研试题【选择题】一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是：A、23415B、54132C、23145D、15432B课堂练习55.2栈的抽象数据类型定义ADTStack{实例元素线性表，栈底

3、，栈顶操作Create();//创建一个空的堆栈IsEmpty();//如果栈为空，返回true，否则返回falseIsFull();//如果栈满，返回true，否则返回falseTop();//返回栈顶元素Push(x);//向栈中添加元素xPop();//删除栈顶元素}6栈结构的应用（资料来源：中国知网www.cnki.net）7栈结构的应用（续）（资料来源：中国知网www.cnki.net）85.3栈的公式化描述（顺序栈）-栈可以看成是受限的线性表:参考线性表描述，令栈顶元素存储在element[

4、length-1]中，栈底元素存储在element[0]中；从LinearList类派生，继承方式采用private。从LinearList的共享成员和保护成员可以被Stack类成员访问，私有成员不可以被Stack的类成员访问。91、从LinearList派生的堆栈类（程序5-1）templateclassStack:privateLinearList{public:Stack(intMaxStackSize=10):LinearList(MaxStackSize){}boo

5、lIsEmpty()const{returnLinearList::IsEmpty();}boolIsFull()const{return(Length()==GetMaxSize());}10TTop()const{if(IsEmpty())throwOutOfBounds());Tx;Find(Length(),x);returnx;}Stack&Push(constT&x){Insert(Length(),x);//插入到最右端return*this;}Stack&Pop(T&x

6、){LinearList::Delete(Length(),x);//从最右端删除return*this;}};11-从LinearList派生的堆栈类Stack的优缺点从LinearList派生的优点代码简洁、易于开发可靠性高、调试工作小容易将栈改成别的实现方式，只需要修改基类即可。从LinearList派生的缺点效率低122、自定义Stack类把Stack定义成一个基类堆栈元素存储在数组中堆栈元素：stack[0:stackTop].栈顶元素：stack[stackTop].栈底元素：stac

7、k[0].堆栈为空：stackTop=-1.堆栈元素个数：stackTop+113自定义Stack类（程序5-2）templateclassclassStack{public:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stack&Push(constT&x);Stack<

8、T>&Pop(T&x)private:inttop;//栈顶intMaxTop;//最大的栈顶值T*stack;//栈元素数组};14操作1-构造空栈templateStack::Stack(intMaxStackSize){MaxTop=MaxStackSize–1;stack=newT[MaxStackSize];top=-1;}15操作2-进栈（插入）进栈实例16进栈（插入）算法templateS