top→b top一a top→空栈 a进栈 b进栈 top- top- edcba to p b edcba e进栈 ∫进栈濫出 e退栈
top 空栈 top top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 a b d e e 退栈 c
top cba top-b b top d退栈 C退栈 b退栈 top-a退栈top→空栈
top c 退栈 b 退栈 a b a a 退栈 空栈 top a b d d 退栈 c top a b c top top
int Push (SeqStack *S, Stack Data x)i /若栈满返回0.否则新元素ⅹ进栈并返回1 if( StackFull (S)) return 0 S->data++S->top]=x;/加入新元素 return 1 int Gettop(SeqStack *S, Stack Data &x)t 若栈空返回0.否则栈顶元素读到X并返回1 if( Stack Empty(s)) return 0; x=S->data[S->top; return 1
int Push (SeqStack *S, StackData x) { //若栈满返回0, 否则新元素 x 进栈并返回1 if ( StackFull (S) ) return 0; S->data[++S->top] = x; //加入新元素 return 1; } int Gettop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; x = S->data[S->top]; return 1; }
int pop (SeqStack*S, Stack Data &x)i /若栈空返回0.否则栈顶元素退出到x并返回1 if( Stack Empty(S)) return O x=S->data s->top-- return 1 双栈共享一个栈空间 0 maxSize-1 data t0]{1
b[0] t[0] t[1] b[1] 0 maxSize-1 data int pop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; x = S->data[S->top--]; return 1; } 双栈共享一个栈空间
双栈处理 两个栈共享一个数组空间 VImaxSizel 设立栈顶指针数组t2和栈底指针数组b2 ti和b分别指示第i个栈的栈顶与栈底 初始t0]=b[0]=-1 t1=b1=maxsize 栈满条件:t0+1=t1 栈顶指针相遇 栈空条件:t0=b0或t=bl ∥栈顶指针退到栈底
双栈处理 ◼ 两个栈共享一个数组空间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] //栈顶指针退到栈底