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

1、信息技术科学学院第第5 5章章 堆栈堆栈-后进先出：一种操作受限的线性表后进先出：一种操作受限的线性表信息技术科学学院主要内容主要内容 堆栈的定义堆栈的定义 堆栈的描述堆栈的描述 公式化描述公式化描述 链表描述链表描述 堆栈的应用堆栈的应用 括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排 迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类2信息技术科学学院堆栈定义堆栈定义DCBA栈顶EpushABCDE栈顶ABCDE栈顶ExtopABCDE栈顶popExtopABCD栈顶栈底 堆栈堆栈（stackstack）是一个）是一个线性表线性表，其其插入插入和和删除删除操作都在表的操

2、作都在表的同一端同一端进行，这进行，这端被称为端被称为栈顶栈顶（toptop），），另一端被称为另一端被称为栈底栈底（bottombottom） LIFOLIFOLast in, First outLast in, First out信息技术科学学院信息技术科学学院5信息技术科学学院抽象数据类型抽象数据类型抽象数据类型抽象数据类型StackStack 实例实例元素线性表，栈底，栈顶元素线性表，栈底，栈顶操作操作CreateCreate()()：创建一个空的堆栈：创建一个空的堆栈IsEmptyIsEmpty()()：如果堆栈为空，则返回：如果堆栈为空，则返回truetrue，否则返回，否则返回f

3、alsefalseIsFullIsFull()()：如果堆栈满，则返回：如果堆栈满，则返回truetrue，否则返回，否则返回falsefalseTopTop()()：返回栈顶元素：返回栈顶元素PushPush( (x x) )：向堆栈中添加元素：向堆栈中添加元素x xPopPop( (x x) )：删除栈顶元素，并将它传递给：删除栈顶元素，并将它传递给x x 信息技术科学学院主要内容主要内容 堆栈的定义堆栈的定义 堆栈的描述堆栈的描述 公式化描述公式化描述 链表描述链表描述 堆栈的应用堆栈的应用 括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排 迷宫、开关盒布线、离线等价类迷宫、

4、开关盒布线、离线等价类7信息技术科学学院公式化描述：继承线性表公式化描述：继承线性表templateclass Stack : private LinearList / LIFO objects public: Stack(int MaxStackSize = 10) : LinearList (MaxStackSize) bool IsEmpty() const return LinearList:IsEmpty(); bool IsFull() const return (Length() = GetMaxSize(); 线性表尾部作为栈顶信息技术科学学院公式化描述（续）公式化描述（续）

5、T Top() const if (IsEmpty() throw OutOfBounds(); T x; Find(Length(), x); return x; Stack& Push(const T& x) Insert(Length(), x); return *this; Stack& Pop(T& x) Delete(Length(), x); return *this;取栈顶提取最后一个元素压栈添加到表尾出栈提取最后一个元素信息技术科学学院实现方法分析实现方法分析 IsFullIsFull需要获取数组大小需要获取数组大小 方法一方法一将类将类Lin

6、earListLinearList的成员的成员MaxSizeMaxSize变为变为protectedprotected类型类型 方法二：方法二：LinearListLinearList类增加函数类增加函数protected: int GetMaxSize() const return MaxSize;LinearListLinearList类的变化不会影响类的变化不会影响StackStack类，更好！类，更好！信息技术科学学院实现方法分析实现方法分析 继承方式为什么是继承方式为什么是privateprivate？ privateprivate继承会把基类的所有成员变为派生类的私有继承会把基类的

7、所有成员变为派生类的私有成员成员 栈虽可看作线性表的特例，但毕竟不是栈虽可看作线性表的特例，但毕竟不是 用户使用用户使用StackStack类，我们希望他们使用类，我们希望他们使用PushPush、PopPop，而不是，而不是InsertInsert、DeleteDelete 而而privateprivate继承恰好可使继承恰好可使InsertInsert、DeleteDelete成为成为StackStack的私有成员，用户无法看到的私有成员，用户无法看到信息技术科学学院StackStack的效率的效率 构造函数、析构函数与构造函数、析构函数与LinearListLinearList相同相同

8、T T：基本类型，：基本类型，(1)(1) T T：用户自定义类，：用户自定义类， (MaxStackSize)(MaxStackSize) 其他函数：其他函数：(1)(1)信息技术科学学院H1.H1.自定义的自定义的StackStack类类templateclass Stack public: Stack(int MaxStackSize = 10); Stack() delete stack; bool IsEmpty() const return top = -1; bool IsFull() const return top = MaxTop; T Top() const; Stack

9、& Push(const T& x); Stack& Pop(T& x);private: int top; / current top of stack int MaxTop; / max value for top T *stack; / element array;信息技术科学学院构造函数构造函数templateStack:Stack(int MaxStackSize)/ Stack constructor. MaxTop = MaxStackSize - 1; stack = new TMaxStackSize; top = -1;空栈信息技术科学学院T

10、opTop函数函数templateT Stack:Top() const/ Return top element. if (IsEmpty() throw OutOfBounds(); return stacktop;信息技术科学学院PushPush函数函数templateStack& Stack:Push(const T& x)/ Push x to stack. if (IsFull() throw NoMem(); / Push fails stack+top = x; return *this;信息技术科学学院PopPop函数函数templateStack& S

11、tack:Pop(T& x)/ Delete top element and put in x. if (IsEmpty() throw OutOfBounds(); x = stacktop-; return *this;信息技术科学学院数组描述缺陷数组描述缺陷 与线性表数组描述类似，空间利用率低与线性表数组描述类似，空间利用率低 两个堆栈特例，空间利用率较高两个堆栈特例，空间利用率较高 PushPush最坏情况（数组满）仍为最坏情况（数组满）仍为(ArraySize)(ArraySize) Pop Pop (1)(1)信息技术科学学院主要内容主要内容 堆栈的定义堆栈的定义 堆栈的描

12、述堆栈的描述 公式化描述公式化描述 链表描述链表描述 堆栈的应用堆栈的应用 括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排 迷宫、开关盒布线、离线等价类迷宫、开关盒布线、离线等价类19信息技术科学学院链表描述链表描述 栈顶在链表哪一端？栈顶在链表哪一端？ 尾节点尾节点 Push(x)Insert(n, x)Push(x)Insert(n, x)： (n)(n) Pop(x)Delete(n, x)Pop(x)Delete(n, x)： (n)(n) 首节点首节点 Push(x)Insert(0, x)Push(x)Insert(0, x)： (1)(1) Pop(x)Delete

13、(1, x)Pop(x)Delete(1, x)： (1)(1)信息技术科学学院LinkedStackLinkedStack类类templateclass LinkedStack : private Chain public: bool IsEmpty() const return Chain:IsEmpty(); bool IsFull() const; T Top() const if (IsEmpty() throw OutOfBounds(); T x; Find(1, x); return x; 信息技术科学学院LinkedStackLinkedStack类类 LinkedStack

14、& Push(const T& x) Insert(0, x); return *this; LinkedStack& Pop(T& x) Delete(1, x); return *this; ;信息技术科学学院IsFullIsFull函数函数templatebool LinkedStack:IsFull() const/Is stack full? try ChainNode *p = new ChainNode; delete p; return false; catch (NoMem) return true; 笨拙！笨拙！信息技术科学学院H2.H2.自

15、定义的链表实现自定义的链表实现template class Node friend LinkedStack; private: T data; Node *link;信息技术科学学院自定义的链表实现（续）自定义的链表实现（续）templateclass LinkedStack public: LinkedStack() top = 0; LinkedStack(); bool IsEmpty() const return top = 0; bool IsFull() const; T Top() const; LinkedStack& Push(const T& x); Lin

16、kedStack& Pop(T& x); private: Node *top; / pointer to top node;信息技术科学学院析构函数析构函数templateLinkedStack:LinkedStack()/ Stack destructor. Node *next; while (top) next = top-link; delete top; top = next; 信息技术科学学院IsFullIsFull函数函数templatebool LinkedStack:IsFull() const/ Is the stack full? try Node *p

17、 = new Node; delete p; return false; catch (NoMem) return true;信息技术科学学院TopTop函数函数templateT LinkedStack:Top() const/ Return top element. if (IsEmpty() throw OutOfBounds(); return top-data;信息技术科学学院PushPushtemplateLinkedStack& LinkedStack:Push(const T& x)/ Push x to stack. Node *p = new Node; p

18、-data = x; p-link = top; top = p; return *this;信息技术科学学院PopPoptemplateLinkedStack& LinkedStack:Pop(T& x)/ Delete top element and put it in x. if (IsEmpty() throw OutOfBounds(); x = top-data; Node *p = top; top = top-link; delete p; return *this;信息技术科学学院H1-2H1-2小结小结 堆栈的两种实现方式堆栈的两种实现方式31公式化公式化链

19、表链表Create()(1)/(MaxSize)(1)/(MaxSize)(1)(1)Destroy()(1)/(MaxSize)(1)/(MaxSize)(n)(n)IsEmpty()(1)(1)(1)(1)IsFull()(1)(1)(1)(1)Top()(1)(1)(1)(1)Push()(1)(1)(1)(1)Pop()(1)(1)(1)(1)信息技术科学学院主要内容主要内容 堆栈的定义堆栈的定义 堆栈的描述堆栈的描述 公式化描述公式化描述 链表描述链表描述 堆栈的应用堆栈的应用 括号匹配、汉诺塔、火车车厢重排括号匹配、汉诺塔、火车车厢重排 迷宫、开关盒布线、离线等价类迷宫、开关盒布线

20、、离线等价类32信息技术科学学院括号匹配括号匹配 (a(a* *(b+c)+d)+(e-b)(b+c)+d)+(e-b)符合语法符合语法 (a+b)(a+b) )( (不符合语法不符合语法 寻找匹配括号对寻找匹配括号对正确处理正确处理和未匹配括号和未匹配括号错误报告错误报告 括号匹配是一个基础问题，可以引申到括号匹配是一个基础问题，可以引申到 C+C+编译器编译器 数学公式自动求解数学公式自动求解信息技术科学学院34信息技术科学学院35信息技术科学学院算法设计思路算法设计思路 ( a ( a * * ( b + c ( b + c ) ) + d ) + (e - b)+ d ) + (e -

21、 b)，匹配括号，匹配括号的规律？的规律？ 右括号与谁匹配（如果有的话）？右括号与谁匹配（如果有的话）？ 由左至右处理符号的话，由左至右处理符号的话，“右右”“后后”，靠后的先匹配靠后的先匹配LIFOLIFO 用一个栈保存未匹配的左括号用一个栈保存未匹配的左括号 由左至右扫描表达式串，遇左括号，由左至右扫描表达式串，遇左括号，pushpush 遇右括号，与栈顶左括号匹配，遇右括号，与栈顶左括号匹配，poppop嵌套或者并列最近（右）未匹配左括号信息技术科学学院匹配失败的情况匹配失败的情况 ( a + b ) ( a + b ) ) ) ( (失败情况的规律失败情况的规律 两种情况对应栈中情况两

22、种情况对应栈中情况右括号之前无与之匹配的左括号左括号之后无与之匹配的右括号遇到一个右括号时，无未匹配的左括号栈空右括号都处理完时，还有未匹配的左括号表达式串处理完时，栈不空信息技术科学学院括号匹配程序括号匹配程序#include #include #include #include stack.hconst int MaxLength = 100; / max expression length信息技术科学学院括号匹配程序（续）括号匹配程序（续）void PrintMatchedPairs(char *expr)/ Parenthesis matching. Stack s(MaxLength

23、); int j, length = strlen(expr); / scan expression expr for ( and ) for (int i = 1; i = length; i+) if (expri - 1 = () s.Push(i);信息技术科学学院括号匹配程序（续）括号匹配程序（续） else if (expri - 1 = ) try s.Pop(j); / unstack match cout j i endl; catch (OutOfBounds) cout No match for right parenthesis” at i endl; 信息技术科学学院

24、括号匹配程序（续）括号匹配程序（续） / remaining ( in stack are unmatched while (!s.IsEmpty() s.Pop(j); cout No match for left parenthesis at j endl;信息技术科学学院括号匹配程序（续）括号匹配程序（续）void main(void) char exprMaxLength; cout Type an expression of length at most MaxLength endl; cin.getline(expr, MaxLength); cout The pairs of m

25、atching parentheses in” endl; puts(expr); cout are 0) TowersOfHanoi(n-1, x, z, y); cout Move top disk from tower x to top of tower y endl; TowersOfHanoi(n-1, z, y, x); moves(n)=2moves(n)=2n n-1-1最少次数，最少次数，(2(2n n) )0, 1) 1(20, 0)(nnmovesnnmoves信息技术科学学院汉诺塔的栈实现汉诺塔的栈实现#include #include #include stack.h

26、“#include stack.h“class Hanoi class Hanoi friend void TowersOfHanoi(int); friend void TowersOfHanoi(int); public: public: void TowersOfHanoi(int n, int x, int y, int z); void TowersOfHanoi(int n, int x, int y, int z); private: private: Stack Stack * *S4; / array of pointers to stacksS4; / array of p

27、ointers to stacks;信息技术科学学院汉诺塔的栈实现汉诺塔的栈实现void Hanoi:TowersOfHanoi(int n, int x, int y, int z)void Hanoi:TowersOfHanoi(int n, int x, int y, int z) int d; / disk number int d; / disk number if (n 0) if (n 0) TowersOfHanoi(n-1, x, z, y); TowersOfHanoi(n-1, x, z, y); Sx-Pop(d); / remove a disk from x Sx-

28、Pop(d); / remove a disk from x Sy-Push(d); / put this disk on tower y Sy-Push(d); / put this disk on tower y cout Move disk d from tower cout Move disk d from tower x to tower y endl; x to tower y endl; TowersOfHanoi(n-1, z, y, x); TowersOfHanoi(n-1, z, y, x); 信息技术科学学院汉诺塔栈实现汉诺塔栈实现void TowersOfHanoi(

29、int n)void TowersOfHanoi(int n)/ Preprocessor for Hanoi:TowersOfHanoi./ Preprocessor for Hanoi:TowersOfHanoi. Hanoi X; Hanoi X; X.S1 = new Stack (n); X.S1 = new Stack (n); X.S2 = new Stack (n); X.S2 = new Stack (n); X.S3 = new Stack (n); X.S3 = new Stack (n); for (int d = n; d 0; d-) / initialize fo

30、r (int d = n; d 0; d-) / initialize X.S1-Pop(d); / add disk d to tower 1 X.S1-Pop(d); / add disk d to tower 1 X.TowersOfHanoi(n, 1, 2, 3); X.TowersOfHanoi(n, 1, 2, 3); 信息技术科学学院汉诺塔栈实现汉诺塔栈实现void main(void)void main(void) cout Moves for a three disk problem are endl; cout Moves for a three disk problem

31、 are 3，H299：次序不对，3，6，H3信息技术科学学院继续继续 入：入：581742581742出：出：H1H2H33692：次序不对，22，42，74，79H37信息技术科学学院继续继续 入：入：581581出：出：H1H2H33692471：次序对出轨1H1：2出轨，3出轨2 38：次序不对，H18H2：4出轨4信息技术科学学院继续继续 入：入：5 5出：出：H1H2H36971 2 3 485：次序对出轨5H2：6出轨6H3：7出轨7H1：8出轨8H3：9出轨，OK!9信息技术科学学院重排算法重排算法 缓冲轨后进先出，用堆栈保存车厢号缓冲轨后进先出，用堆栈保存车厢号 考虑在出轨顺

32、序，必须栈底大，栈顶小考虑在出轨顺序，必须栈底大，栈顶小 依次检查入轨车厢编号依次检查入轨车厢编号 如果如果出轨所需要的下一车厢，出轨所需要的下一车厢，缓冲轨缓冲轨 依次检查缓冲轨，若新来的依次检查缓冲轨，若新来的 栈顶，入栈栈顶，入栈 如果如果= =出轨所需要的下一车厢，出轨所需要的下一车厢，出轨出轨 缓冲轨中车厢可能满足出轨需要，检查缓冲轨栈顶车厢，如缓冲轨中车厢可能满足出轨需要，检查缓冲轨栈顶车厢，如有可能，出栈，有可能，出栈，出轨，不是一次，要反复做，直至栈中无出轨，不是一次，要反复做，直至栈中无满足出轨需要的车厢满足出轨需要的车厢信息技术科学学院重排程序重排程序bool Railro

33、ad(int p, int n, int k)/ k track rearrangement of car order p1:n. / Return true if successful, false if impossible. / Throw NoMem exception if inadequate space. / create stacks for holding tracks LinkedStack *H; H = new LinkedStack k + 1; int NowOut = 1; / next car to output int minH = n+1; / smalle

34、st car in a track int minS; / track with car minHk=?为什么不是Stack？信息技术科学学院重排程序（续）重排程序（续）/ rearrange cars for (int i = 1; i = n; i+) if (pi = NowOut) / send straight out cout “Move car ” pi “ from input to output”; cout endl; NowOut+; while (minH = NowOut) Output(minH, minS, H, k, n); NowOut+; 信息技术科学学院重

35、排程序（续）重排程序（续） else / put car pi in a holding track if (!Hold(pi, minH, minS, H, k, n) return false; return true;信息技术科学学院OutputOutput：缓冲铁轨：缓冲铁轨出轨出轨void Output(int& minH, int& minS, LinkedStack H, int k, int n)/ Move from hold to output and update minH and minS. int c; / car index / delete sma

36、llest car minH from stack minS HminS.Pop(c); cout Move car minH from holding track “ minS to output endl;信息技术科学学院OutputOutput：缓冲铁轨：缓冲铁轨出轨出轨 / find new minH and minS / by checking top of all stacks minH = n + 2; for (int i = 1; i = k; i+) if (!Hi.IsEmpty() &(c = Hi.Top() minH) minH = c; minS = i;

37、信息技术科学学院HoldHold：入轨：入轨缓冲铁轨缓冲铁轨bool Hold(int c, int& minH, int &minS, LinkedStack H, int k, int n)/ Add car c to a holding track./ find best holding track for car c / initialize int BestTrack = 0, / best track so far BestTop = n + 1, / top car in BestTrack x; / a car index信息技术科学学院HoldHold：入轨：

38、入轨缓冲铁轨（续）缓冲铁轨（续） for (int i = 1; i = k; i+) if (!Hi.IsEmpty() / track i not empty x = Hi.Top(); if (c x & x BestTop) BestTop = x; BestTrack = i; else / track i empty if (!BestTrack) BestTrack = i; if (!BestTrack) return false; / no feasible track信息技术科学学院HoldHold：入轨：入轨缓冲铁轨（续）缓冲铁轨（续） / add c to best track HBestTrack.Push(c); cout Move car c from input to holding track BestTrack endl; /