如何合理进行栈空间分配，以避免栈谥 出或空间的浪费？ ·双栈共享一个栈空间（多栈共享栈空间） •栈的链接存储方式 一链式栈 11
• 双栈共享一个栈空间（多栈共享栈空间） 如何合理进行栈空间分配，以避免栈溢 出或空间的浪费？ • 栈的链接存储方式—— 链式栈 11
双栈共享一个栈空间 maxSize-1 b[0] t[0] [1] 6[1] 两个栈共享一个数组空间V[maxSize] 设立栈顶指针数组2]和栈底指针数组b[2] t和b分别指示第i个栈的栈顶与栈底 初始0]=b0]=-1,t1]=b[1小=maxSize 栈满条件：0]+1=t1] /栈顶指针相遇 栈空条件：0]=b0]或1]=b[1] /栈顶指针退到栈底
◼ 两个栈共享一个数组空间V[maxSize] ◼ 设立栈顶指针数组 t[2] 和栈底指针数组 b[2] t[i]和b[i]分别指示第 i 个栈的栈顶与栈底 ◼ 初始 t[0] = b[0] = -1, t[1] = b[1] = maxSize ◼ 栈满条件：t[0]+1 == t[1] //栈顶指针相遇 ◼ 栈空条件：t[0] = b[0]或t[1] = b[1] //栈顶指针退到栈底 双栈共享一个栈空间 12
bool Push(DualStack&DS,E x,int i) if (DS.t[0]+1 --DS.t[1])return false; if (i==0)DS.t[0]++;else DS.t[1]--; DS.V[DS.t[=x; return true; bool Pop(DualStack&DS,E x,int i) if (DS.t[i]=DS.b[il)return false; x DS.V[DS.t[i] if (i==0)DS.t[0]--;else DS.t[1]++; return true; 3 13
bool Push(DualStack& DS, E x, int i) { if (DS.t[0]+1 == DS.t[1]) return false; if (i == 0) DS.t[0]++; else DS.t[1]--; DS.V[DS.t[i]] = x; return true; } bool Pop(DualStack& DS, E & x, int i) { if (DS.t[i] == DS.b[i]) return false; x = DS.V[DS.t[i]]; if (i == 0) DS.t[0]--; else DS.t[1]++; return true; } 13
栈的链接表示一链式栈 top 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 14
栈的链接表示 — 链式栈 • 链式栈无栈满问题，空间可扩充 • 插入与删除仅在栈顶处执行 • 链式栈的栈顶在链头 14
链式栈(LinkedStack)类的定义 #include <iostream.h> #include“stack.h” template <class E> struct StackNode /栈结点类定义 private: E data; /栈结点数据 StackNode<E>*link; 川结点链指针 public: StackNode(E d=0,StackNode<E>*next NULL) data(d),link(next) } 15
15 链式栈 (LinkedStack)类的定义 #include <iostream.h> #include “stack.h” template <class E> struct StackNode { //栈结点类定义 private: E data; //栈结点数据 StackNode<E> *link; //结点链指针 public: StackNode(E d = 0, StackNode<E> *next = NULL) : data(d), link(next) { } };