堆栈 (STACKS)—Restricted version of a linear list 第 5 章 堆栈 (STACKS)—Restricted version of a linear list

Contents 5.1 The Abstract Data Type 5.2 Derived Classes and Inheritance 派生类和继承 5.3 Formula-Based Representation 栈的公式化描述 5.4 Linked Representation 栈的链表描述 5.5 Applications 应用

5.1 The Abstract data type Definition A stack is a linear list in which insertion(addition) and deletion take place at the same end, The end is called top. The other end of the list is called the bottom e1, e2, e3, …, ei, …, en-1, en ↑ ↑ bottom top

Insert() Delete Delete Stack configurations E ←top D C B A ←bottom D ←top C B A ←bottom D ←top C B A ←bottom C ←top B A ←bottom Insert() Delete Delete Stack is a table of LIFO (Last-In, First-Out) .

Stack ADT AbstractDataType Stack { instances linear list of elements; one end is called bottom; the other is the top 操作 Create( )；create an empty stack; IsEmpty( )；return true if stack if empty，false otherwise IsFull( )；return true if stack is full，false otherwise Top( )；return the top element of stack Add(x)；add element x to the stack. Delete(x)；delete top element of stack and put it in x. }

5.2 Derive class and inheritance(派生类和继承) A Class B that is a specialized or restricted version of another class A may be derived (派生）from the class. A is called Based class and B the derived class. B inherits (继承） all of the members –public, protected and private of A, and all data members and functions of A are associated with every object of type B. Furthermore a class can be derived from more than one class, e.g. from A,C .

Three ways to inherent Using class header syntax (语法） to specify class B: public A //public Class B inherent all public and protected members of A class B: public A, private C Class B inherent the public and protected members of A, but all the public and protected members of C become the private members of B. class B: protected A All public and protected member of A become the protected member of B. NOTE: in all model of inheritance, the private members of A remain private to A and are not accessible from members of B.

usage If X is of type B, we can use function F on X by writing X.F () only when F is a public member of either B or A.

5.3 formula-based representation Since a stack is a linear list with the restriction that additions and deletions take place and the same end. If we use formula-based representation, top element of stack= elemenet[length-1]; and bottom=element[0] The class stack defined in Program 5.1 is a derived class of LinearList( Program 3.1), where the inheritance model is private, it means that the public and protected members of LinearList are accessible bu members of Stack, but not by stack instances.

1. Program 3.1 template <class T> class LinearList { //公式化描述的线性表 public: LinearList(int MaxListSize = 10); ~LinearList() { delete [] element; } bool IsEmpty() const { return length == 0; } int Length() const { return length; } bool Find(int k, T& x) const; int Search(const T& x) const; LinearList<T>& Delete(int k, T& x); LinearList<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: int length; int MaxSize; T *element; };

栈顶元素  element[length-1] 栈底元素  element[0] 映射公式：location(i）=i-1 5 2 4 8 1 element 0 1 2 3 4 MaxSize-1 length=5 top bottom 栈顶元素  element[length-1] 栈底元素  element[0]

Program 5.1 template<class T> class Stack : private LinearList <T> { public: Stack(int MaxStackSize = 10) : LinearList<T> (MaxStackSize) {} bool IsEmpty() const {return LinearList<T> :: IsEmpty();} bool IsFull() const {return (Length() == GetMaxSize());} T Top() const {if (IsEmpty()) throw OutOfBounds(); T x; Find(Length(), x); return x;} Stack<T>& Add(const T& x) {Insert(Length(), x); return *this;} Stack<T>& Delete(T& x) {LinearList<T>::Delete(Length(), x); return *this;} };

Private inherence The public and protected member of linearList become private to Stack, but the private member of LinearList are not accessible to members of Stack. The constructor for Stack simply invokes the linear list constructor processing to it the desired stack size MaxStackSize. When object of type Stack are to be destroyed, the destructor for LinearList will be invoked automatically.

The IsEmpty function is simply a call to the corresponding function for a linear list, we use the scope resolution operator :: to distinguish between functions and members that have the same name in the base and derived class. Since MaxSize is private in LinearList, we add a protect function GetMaxSize() in Stack to acess the value of MaxSize.

template <class T> class LinearList { public: …… protected: int GetMaxSize() const {return MaxSize;} private: int length; int MaxSize; T *element; };

Efficiency of Stack 时间复杂性：略 从LinearList派生Stack： 优点： 大大减少了编码量。 使程序的可靠性得到很大提高 。 缺点： 运行效率降低。例：向堆栈中添加一个元素。 派生类Stack也会受到LinearList本身所受限制的影响。例如，必须为数据类型为T的成员定义操作符<<和== 。

2. 自定义 Customized Stack template<class T> class 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<T>& Add(const T& x); // push Stack<T>& Delete(T& x); // pop private: int top; int MaxTop; T *stack; };

2. 自定义Stack 5 2 4 8 1 stack 0 1 2 3 4 MaxTop top=4 堆栈容量: MaxTop+1

5 2 4 8 1 stack 0 1 2 3 4 MaxTop top=4 template<class T> Stack<T>::Stack(int MaxStackSize) { // 构造函数 MaxTop = MaxStackSize – 1; stack = new T[MaxStackSize]; top = -1; } template<class T>// return the element at the top T Stack<T>::Top() const { if (IsEmpty()) throw OutOfBounds(); else return stack[top]; }

5 2 4 8 1 stack 0 1 2 3 4 MaxTop top=4 template<class T> Stack<T>& Stack<T>::Add(const T& x) { if (IsFull()) throw NoMem(); stack[++top] = x; return *this; } template<class T> Stack<T>& Stack<T>::Delete(T& x) { if (isEmpty()) throw OutOfBounds(); x = stack[top--]; return *this; }

Comparison In a run-time test that involved a for with 100,000 stack add and deletion operations, program 5.1 took 50% more time than did by program 5.2.

5.4 Linked Representation 当同时使用多个堆栈时: 浪费大量的空间 若仅同时使用两个堆栈，则是一种例外。 如何在一个数组中描述两个堆栈?

在一个数组中描述两个堆栈

5.4 栈的链表描述 1. 使用一个链表来描述一个堆栈（从chain派生） 链表的哪一端对应于栈顶? ……. 把链表的右端作为栈顶 5.4 栈的链表描述 1. 使用一个链表来描述一个堆栈（从chain派生） 链表的哪一端对应于栈顶? ……. first 把链表的右端作为栈顶 stack: add(x)  Insert(n,x) (n 为链表中的节点数目 ) stack: delete(x)  Delete(n,x) 时间复杂性 : Q(n) 把链表的左端作为栈顶 stack: add(x)  Insert(0,x) stack: delete(x)  Delete(1,x) 时间复杂性 : Q(1)

类‘Chain’ template <class T> class Chain { public: Chain() { first = 0; } ~Chain(); bool IsEmpty() const { return first == 0; } int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Chain<T>& Delete(int k, T& x); Chain<T>& Insert(int k, const T& x); void Output(ostream& out) const; private: ChainNode<T> *first; };

template<class T> class LinkedStack : private Chain<T> { public: bool IsEmpty() const {return Chain<T>::IsEmpty();} bool IsFull() const; T Top() const {if (IsEmpty()) throw OutOfBounds(); T x; Find(1, x); return x;} LinkedStack<T>& Add(const T& x) {Insert(0, x); return *this;} LinkedStack<T>& Delete(T& x) {Chain<T>::Delete(1, x); return *this;} } ; bool LinkedStack<T>::IsFull() const {// 堆栈是否满? try {ChainNode<T> *p = new ChainNode<T>; delete p; return false;} catch (NoMem) {return true;} }

2. 自定义链表形式的堆栈 Definition of nodes of stack template <class T> 2. 自定义链表形式的堆栈 ……. top Definition of nodes of stack template <class T> class Node{ friend LinkedStack<T>; private: T data; Node<T> *link; } ;

Class LinkedStack template<class T> class LinkedStack {// 构建函数 public: LinkedStack () {top = 0;} ~LinkedStack(); bool IsEmpty() const {return top= =0;} bool IsFull() const; T Top() const; LinkedStack<T>& Add(const T& x); LinkedStack<T>& Delete(T& x); private: Node<T> *top; // 指向栈顶节点 }

析构函数 Template<class T> LinkedStack<T>::~LinkedStack() {// Stack destructor.. Node<T> *next; while (top) { next = top->link; delete top; top = next; }

IsFull function Template<class T> LinkedStack<T>::IsFull() const {// Is the stack full? try { Node<T> *p = new Node<T>; delete p; return false;} catch (NoMem) {return true; } }

Top Template<class T> T LinkedStack<T>::Top() const {// return top element if (Isempty()) throw OutOfBounds(); return top->data; }

Add Template<class T> LinkedStack<T>& LinkedStack<T>::Add(const T& x) {// add x to stack Node<T> *p= new Node<T>; p->data = x; p->link = top; top = p; return *this; }

Delete Template<class T> LinkedStack<T>& LinkedStack<T>::Delete(T& x) {// delete top element and put in x if (IsEmpty()) throw OutOfBounds(); x = top->data; Nodde<T> *p = top; top = top->link; delete p; return *this; }

5.5 应用 5.5.1 括号匹配 5.5.2 汉诺塔 5.5.3 火车车厢重排 5.5.4 开关盒布线 5.5.5 离线等价类问题 5.5 应用 5.5.1 括号匹配 5.5.2 汉诺塔 5.5.3 火车车厢重排 5.5.4 开关盒布线 5.5.5 离线等价类问题 5.5.6 迷宫老鼠

5.5.1 括号匹配 问题:匹配一个字符串中的左、右括号 (a*(b+c)+d) (a+b))*((c+d) 4 8 1 10 1 5 4 8 1 10 (a+b))*((c+d) 1 5 No match for right parenthesis at 6 9 12 No match for left parenthesis at 8

括号匹配 实现思路： 1.从左至右扫描一个字符串 2.每当遇到一个左括号时，把所遇到的左括号的位置存放到堆栈内。 3.每当遇到一个右括号时，查看栈顶是否为左括号（如果存在），有则匹配，同时从栈顶删除相匹配的左括号。没有则输出左括号不匹配。 若能扫描结束并且栈为空，输出括号匹配，否则输出右括号不匹配。

括号匹配 #include <iostream.h> #include <string.h> #include <stdio.h> #include "stack.h" const int MaxLength = 100; // 最大的字符串长度 void PrintMatchedPairs(char *expr) {// 括号匹配 Stack<int> s(MaxLength) ; int j, length = strlen(expr);

括号匹配 // 从表达式expr 中搜索‘( ’‘和)’ for (int i = 1; i<=length; i++) { if (expr[i -1] = =' ( ' ) s.Add(i); else if (expr[i -1] = =' ) ' ) try { s.Delete(j); cout << j <<' ' << i << endl;} catch (OutOfBounds) { cout << "No match for right parenthesis" << " at " << i << endl;} } // 堆栈中所剩下的(都是未匹配的 while(!s.IsEmpty()) { s.Delete(j); cout << "No match for left parenthesis at " <<j< endl;}

括号匹配程序运行示例 (((a+b)*c+d-e)/(f+g)-(h+j)*(k-1))/(m-n) 12345678910 14 16 20 22 26 1 2 3 stack 16 22 … output 3 7 2 14 16 20 22 26 …

5.5.2 汉诺塔 已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔A的底部堆放至顶部，我们需要把碟子都移动到塔C: 5.5.2 汉诺塔 已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔A的底部堆放至顶部，我们需要把碟子都移动到塔C: 每次移动一个碟子. 任何时候都不能把大碟子放到小碟子的上面。

汉诺塔 void TowersOfHanoi(int n, int x, int y, int z) { / /把n 个碟子从塔x 移动到塔y，可借助于塔z if (n > 0) { TowersOfHanoi(n-1, x,z,y); cout << "Move top disk from tower " << x <<" to top of tower " << y << endl; TowersOfHanoi(n-l, z, y, x);} }

汉诺塔 碟子的移动次数 : moves(n)= 2n-1 时间复杂性: Q(2n ) 0 n=0 2moves(n-1)+1 n>0

塔的状态

塔的状态

塔的状态

塔的状态

塔的状态

塔的状态

塔的状态

塔的状态

汉诺塔 class Hanoi{ friend void TowersOfHanoi(int); public: void TowersOfHanoi(int n, int x, int y, int z); private: Stack<int> *S[4]; } ; void Hanoi::TowersOfHanoi(int n, int x, int y, int z) {// 把n 个碟子从塔x 移动到塔y，可借助于塔z int d; // 碟子编号 if (n > 0) { TowersOfHanoi(n-l, x, z, y); S[x]->Delete(d); //从x中移走一个碟子 S[y]->Add(d); //把这个碟子放到y 上 ShowState(); TowersOfHanoi(n-l, z, y, x);} }

汉诺塔 void TowersOfHanoi(int n) {// Hanoi::towersOfHanoi的预处理程序 Hanoi X； X.S[1] = new Stack<int> (n); X.S[2] = new Stack<int> (n); X.S[3] = new Stack<int> (n); for (int d = n; d > 0; d--) // 初始化 X.S[1]->Add(d); // 把碟子d 放到塔1上 / /把塔1上的n个碟子移动到塔3上，借助于塔2 的帮助 X . TowersOfHanoi(n, 1, 2, 3); }

5.5.3 火车车厢重排 5 8 1 6 3 ……. n n-1 n-2 2 1 ……. 货运列车共有n节车厢，每节车厢将停放在不同的车站 5.5.3 火车车厢重排 5 8 1 6 3 ……. 货运列车共有n节车厢，每节车厢将停放在不同的车站 n个车站的编号分别为1到n 货运列车按照第n站至第1站的次序经过这些车站 车厢的编号与它们的目的地相同。 重新排列车厢，使各车厢从前至后按编号1到n的次序排列。 n n-1 n-2 2 1 …….

火车车厢重排例（3个缓冲铁轨） 初始 最终 缓冲铁轨是按照LIFO的方式使用的 在重排车厢过程中，仅允许以下移动： 初始 最终 缓冲铁轨是按照LIFO的方式使用的 在重排车厢过程中，仅允许以下移动： 车厢可以从入轨的前部（即右端）移动到一个缓冲铁轨的顶部或出轨的左端。 车厢可以从一个缓冲铁轨的顶部移动到出轨的左端。

3个缓冲铁轨中间状态 选择缓冲铁轨的分配规则 k 个链表形式的堆栈来描述k 个缓冲铁轨。 新的车厢u应送入这样的缓冲铁轨：其顶部的车厢编号v 满足v > u，且v 是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。 k 个链表形式的堆栈来描述k 个缓冲铁轨。

实现思路 int NowOut=1； // NowOut:下一次要输出的车厢号 for （int i=1;i<=n;i++）//从前至后依次检查的所有车厢 {1.车厢 p[i] 从入轨上移出 2.If (p[i] == NowOut) ①把p[i]放到出轨上去 ; NowOut++; ② while (minH(当前缓冲铁轨中编号最小的车厢)== NowOut ） {把minH 放到出轨上去； 更新 minH ;NowOut++;} else 按照分配规则将车厢p[i]送入某个缓冲铁轨。 } 读程序 5.8 5.9 5.10