如何合理进行栈空间分配,以避免找溢 出或空间的浪费? 双栈共享一个栈空间(多栈共享栈空间) 栈的链接存储方式—链式栈
• 双栈共享一个栈空间（多栈共享栈空间） 如何合理进行栈空间分配，以避免栈溢 出或空间的浪费？ • 栈的链接存储方式—— 链式栈 11
双栈共享一个栈空间 maxSize-1 b0] b1] 两个栈共享一个数组空间V[ maxSize a设立栈顶指针数组t2和栈底指针数组b2 圳和b分别指示第i个栈的栈顶与栈底 初始t0]=b|0]=-1,t1l=b]= maxsize 栈满条件:t0+1=t1栈顶指针相遇 栈空条件:t0=b0或t=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 it if DS. t([0+1==DS. t[1) return false; if(i==0)Ds. t[0++; else Ds. t[]--; DS.VDS t[l=X return true, bool Pop( ualStack ds,e&x, int i if DS. t 1==DS biD return false X=DS.VDS. t[ll if(i==0)Ds. t[0]--; else Ds. t[1++; return true
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
栈的链接表示一链式栈 op 链式栈无栈满向题,空间可扩充 插入与删除仅在栈顶处执行 ·链式栈的栈顶在链头
栈的链接表示 — 链式栈 • 链式栈无栈满问题，空间可扩充 • 插入与删除仅在栈顶处执行 • 链式栈的栈顶在链头 14
链式栈( LinkedStack)类的定义 #include <iostream.h> nclude“ stack h template <class e> struct StackNode i /栈结点类定义 rivate e data: 栈结点数据 StackNode<e> *link 结点链指针 public StackNode(e d=0, StackNodee> Mnext= NULL datal(d), link(next)
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) { } };