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

信息技术科学学院第5章堆栈----后进先出：一种操作受限的线性表信息技术科学学院主要内容•堆栈的定义•堆栈的描述–公式化描述–链表描述•堆栈的应用–括号匹配、汉诺塔、火车车厢重排–迷宫、开关盒布线、离线等价类2信息技术科学学院堆栈定义DCBA栈顶EpushABCDE栈顶ABCDE栈顶ExtopABCDE栈顶popExtopABCD栈顶栈底•堆栈（stack）是一个线性表，其插入和删除操作都在表的同一端进行，这端被称为栈顶（top），另一端被称为栈底（bottom）•LIFOLastin,Firstout信息技术科学学院信息技术科学学院5信息技术科学学院抽象数据类型抽象数据类型Stack{实例元素线性表，栈底，栈顶操作Create()：创建一个空的堆栈IsEmpty()：如果堆栈为空，则返回true，否则返回falseIsFull()：如果堆栈满，则返回true，否则返回falseTop()：返回栈顶元素Push(x)：向堆栈中添加元素xPop(x)：删除栈顶元素，并将它传递给x}信息技术科学学院主要内容•堆栈的定义•堆栈的描述–公式化描述–链表描述•堆栈的应用–括号匹配、汉诺塔、火车车厢重排–迷宫、开关盒布线、离线等价类7信息技术科学学院公式化描述：继承线性表templateclassTclassStack:privateLinearListT{//LIFOobjectspublic:Stack(intMaxStackSize=10):LinearListT(MaxStackSize){}boolIsEmpty()const{returnLinearListT::IsEmpty();}boolIsFull()const{return(Length()==GetMaxSize());}线性表尾部作为栈顶信息技术科学学院公式化描述（续）TTop()const{if(IsEmpty())throwOutOfBounds();Tx;Find(Length(),x);returnx;}StackT&Push(constT&x){Insert(Length(),x);return*this;}StackT&Pop(T&x){Delete(Length(),x);return*this;}};取栈顶——提取最后一个元素压栈——添加到表尾出栈——提取最后一个元素信息技术科学学院实现方法分析•IsFull需要获取数组大小–方法一将类LinearList的成员MaxSize变为protected类型–方法二：LinearList类增加函数protected:intGetMaxSize()const{returnMaxSize;}LinearList类的变化不会影响Stack类，更好！信息技术科学学院实现方法分析•继承方式为什么是private？–private继承会把基类的所有成员变为派生类的私有成员–栈虽可看作线性表的特例，但毕竟不是–用户使用Stack类，我们希望他们使用Push、Pop…，而不是Insert、Delete–而private继承恰好可使Insert、Delete成为Stack的私有成员，用户无法看到信息技术科学学院Stack的效率•构造函数、析构函数与LinearList相同–T：基本类型，Θ(1)–T：用户自定义类，Θ(MaxStackSize)•其他函数：Θ(1)信息技术科学学院H1.自定义的Stack类templateclassTclassStack{public:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;StackT&Push(constT&x);StackT&Pop(T&x);private:inttop;//currenttopofstackintMaxTop;//maxvaluefortopT*stack;//elementarray};信息技术科学学院构造函数templateclassTStackT::Stack(intMaxStackSize){//Stackconstructor.MaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}空栈信息技术科学学院Top函数templateclassTTStackT::Top()const{//Returntopelement.if(IsEmpty())throwOutOfBounds();returnstack[top];}信息技术科学学院Push函数templateclassTStackT&StackT::Push(constT&x){//Pushxtostack.if(IsFull())throwNoMem();//Pushfailsstack[++top]=x;return*this;}信息技术科学学院Pop函数templateclassTStackT&StackT::Pop(T&x){//Deletetopelementandputinx.if(IsEmpty())throwOutOfBounds();x=stack[top--];return*this;}信息技术科学学院数组描述缺陷•与线性表数组描述类似，空间利用率低•两个堆栈特例，空间利用率较高–Push最坏情况（数组满）仍为Ο(ArraySize)–PopΘ(1)信息技术科学学院主要内容•堆栈的定义•堆栈的描述–公式化描述–链表描述•堆栈的应用–括号匹配、汉诺塔、火车车厢重排–迷宫、开关盒布线、离线等价类19信息技术科学学院链表描述•栈顶在链表哪一端？–尾节点•Push(x)——Insert(n,x)：Θ(n)•Pop(x)——Delete(n,x)：Θ(n)–首节点•Push(x)——Insert(0,x)：Θ(1)•Pop(x)——Delete(1,x)：Θ(1)信息技术科学学院LinkedStack类templateclassTclassLinkedStack:privateChainT{public:boolIsEmpty()const{returnChainT::IsEmpty();}boolIsFull()const;TTop()const{if(IsEmpty())throwOutOfBounds();Tx;Find(1,x);returnx;}信息技术科学学院LinkedStack类LinkedStackT&Push(constT&x){Insert(0,x);return*this;}LinkedStackT&Pop(T&x){Delete(1,x);return*this;}};信息技术科学学院IsFull函数templateclassTboolLinkedStackT::IsFull()const{//Isstackfull?try{ChainNodeT*p=newChainNodeT;deletep;returnfalse;}catch(NoMem){returntrue;}}•笨拙！信息技术科学学院H2.自定义的链表实现templateclassTclassNode{friendLinkedStackT;private:Tdata;NodeT*link;};信息技术科学学院自定义的链表实现（续）templateclassTclassLinkedStack{public:LinkedStack(){top=0;}~LinkedStack();boolIsEmpty()const{returntop==0;}boolIsFull()const;TTop()const;LinkedStackT&Push(constT&x);LinkedStackT&Pop(T&x);private:NodeT*top;//pointertotopnode};信息技术科学学院析构函数templateclassTLinkedStackT::~LinkedStack(){//Stackdestructor..NodeT*next;while(top){next=top-link;deletetop;top=next;}}信息技术科学学院IsFull函数templateclassTboolLinkedStackT::IsFull()const{//Isthestackfull?try{NodeT*p=newNodeT;deletep;returnfalse;}catch(NoMem){returntrue;}}信息技术科学学院Top函数templateclassTTLinkedStackT::Top()const{//Returntopelement.if(IsEmpty())throwOutOfBounds();returntop-data;}信息技术科学学院PushtemplateclassTLinkedStackT&LinkedStackT::Push(constT&x){//Pushxtostack.NodeT*p=newNodeT;p-data=x;p-link=top;top=p;return*this;}信息技术科学学院PoptemplateclassTLinkedStackT&LinkedStackT::Pop(T&x){//Deletetopelementandputitinx.if(IsEmpty())throwOutOfBounds();x=top-data;NodeT*p=top;top=top-link;deletep;return*this;}信息技术科学学院H1-2小结•堆栈的两种实现方式31公式化链表Create()Θ(1)/Θ(MaxSize)Θ(1)Destroy()Θ(1)/Θ(MaxSize)Θ(n)IsEmpty()Θ(1)Θ(1)IsFull()Θ(1)Θ(1)Top()Θ(1)Θ(1)Push()Θ(1)Θ(1)Pop()Θ(1)Θ(1)信息技术科学学院主要内容•堆栈的定义•堆栈的描述–公式化描述–链表描述•堆栈的应用–括号匹配、汉诺塔、火车车厢重排–迷宫、开关盒布线、离线等价类32信息技术科学学院括号匹配•(a*(b+c)+d)+(e-b)——符合语法•(a+b))(——不符合语法•寻找匹配括号对——正确处理和未匹配括号——错误报告•括号匹配是一个基础问题，可以引申到–C++编译器–数学公式自动求解信息技术科学学院34信息技术科学学院35信息技术科学学院算法设计思路•(a*(b+c)+d)+(e-b)，匹配括号的规律？•右括号与谁匹配（如果有的话）？•由左至右处理符号的话，“右”“后”，靠后的先匹配——LIFO–用一个栈保存未匹配的左括号–由左至右扫描表达式串，遇左括号，push–遇右括号，与栈顶左括号匹配，pop嵌套或者并列最近（右）未匹配左括号信息技术科学学院匹配失败的情况•(a+b))(——失败情况的规律•两种情况对应栈中情况右括号之前无与之匹配的左括号左括号之后无与之匹配的右括号遇到一个右括号时，无未匹配的左括号——栈空右括号都处理完时，还有未匹配的左括号——表达式串处理完时，栈不空信息技术科学学院括号匹配程序#includeiostream.h#includestring.h#includestdio.h#includestack.hconstintMaxLength=100;//maxexpressionlength信息技术科学学院括号匹配程序（续）voidPrintMatchedPairs(char*expr){//