堆栈知识详解(简单易懂).ppt

《堆栈知识详解(简单易懂).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章堆栈----后进先出：一种操作受限的线性表主要内容堆栈的定义堆栈的描述公式化描述链表描述堆栈的应用括号匹配、汉诺塔、火车车厢重排迷宫、开关盒布线、离线等价类2堆栈定义DCBA栈顶EpushABCDE栈顶ABCDE栈顶ExtopABCDE栈顶popExtopABCD栈顶栈底堆栈（stack）是一个线性表，其插入和删除操作都在表的同一端进行，这端被称为栈顶（top），另一端被称为栈底（bottom）LIFOLastin,Firstout5抽象数据类型抽象数据类型Stack{实例元素线性表，栈底，栈顶操作Create()：创建一个空的堆栈IsEmpty()：如果堆栈为空，则返回tru

2、e，否则返回falseIsFull()：如果堆栈满，则返回true，否则返回falseTop()：返回栈顶元素Push(x)：向堆栈中添加元素xPop(x)：删除栈顶元素，并将它传递给x}主要内容堆栈的定义堆栈的描述公式化描述链表描述堆栈的应用括号匹配、汉诺塔、火车车厢重排迷宫、开关盒布线、离线等价类7公式化描述：继承线性表templateclassStack:privateLinearList{//LIFOobjectspublic:Stack(intMaxStackSize=10):LinearList(MaxStackSize){}boolIsEmpty

3、()const{returnLinearList::IsEmpty();}boolIsFull()const{return(Length()==GetMaxSize());}线性表尾部作为栈顶公式化描述（续）TTop()const{if(IsEmpty())throwOutOfBounds();Tx;Find(Length(),x);returnx;}Stack&Push(constT&x){Insert(Length(),x);return*this;}Stack&Pop(T&x){Delete(Length(),x);return*this;}};取栈顶——提取最后

4、一个元素压栈——添加到表尾出栈——提取最后一个元素实现方法分析IsFull需要获取数组大小方法一将类LinearList的成员MaxSize变为protected类型方法二：LinearList类增加函数protected:intGetMaxSize()const{returnMaxSize;}LinearList类的变化不会影响Stack类，更好！实现方法分析继承方式为什么是private？private继承会把基类的所有成员变为派生类的私有成员栈虽可看作线性表的特例，但毕竟不是用户使用Stack类，我们希望他们使用Push、Pop…，而不是Insert、Delete而privat

5、e继承恰好可使Insert、Delete成为Stack的私有成员，用户无法看到Stack的效率构造函数、析构函数与LinearList相同T：基本类型，Θ(1)T：用户自定义类，Θ(MaxStackSize)其他函数：Θ(1)H1.自定义的Stack类templateclassStack{public:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stac

6、k&Push(constT&x);Stack&Pop(T&x);private:inttop;//currenttopofstackintMaxTop;//maxvaluefortopT*stack;//elementarray};构造函数templateStack::Stack(intMaxStackSize){//Stackconstructor.MaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}空栈Top函数templateTStack::Top()const{//R

7、eturntopelement.if(IsEmpty())throwOutOfBounds();returnstack[top];}Push函数templateStack&Stack::Push(constT&x){//Pushxtostack.if(IsFull())throwNoMem();//Pushfailsstack[++top]=x;return*this;}Pop函数template