第三章栈和队列 栈( Stack) 队列( Queue) n递归的概念 递归与递归工作栈 n递归与回溯
◼ 栈 ( Stack ) ◼ 队列 ( Queue ) ◼ 递归的概念 ◼ 递归与递归工作栈 ◼ 递归与回溯
栈( Stack) 只允许在一端插入和删除的线性表 允许插入和删除 艮栈进栈 的一端称为栈顶 top),另一端称 top 为栈底( bottom) n-2 △△△△公 特点 0 后进先出(LIFO) bottom
◼ 只允许在一端插入和删除的线性表 ◼ 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) ◼ 特点 后进先出 (LIFO) 栈 ( Stack ) 退栈 进栈 a0 an-1 an-2 top bottom
栈的主要操作 ADT Stack i /对象由数据类型为 StackData的元素构成 int push( (stack*S, StackData x);∥进栈 int Pop( stack*s, StackData&x);/出栈 int GetTop( stack*s, StackData&x);/取栈顶 void Initstack( (stack*S);置空栈 int Stack Empty(sack*S);/判栈空否 int Stack Full(stack*S);/判栈满否
ADT Stack { //对象:由数据类型为StackData的元素构成 int Push (stack *S, StackData x); //进栈 int Pop (stack *S, StackData &x); //出栈 int GetTop (stack *S, StackData &x); //取栈顶 void InitStack (stack *S); //置空栈 int StackEmpty (stack *S); //判栈空否 int StackFull (stack *S); //判栈满否 } 栈的主要操作
栈的数组表示一顺序栈 tdefine stack size 100 typedef char StackData; typedef struct t /顺序栈定义 Stack Data data StackSize;/栈数组 int top: /栈顶指针 3 SeqStack; 0123456789 Stack Size-1 data top(栈空)
#define StackSize 100 typedef char StackData; typedef struct { //顺序栈定义 StackData data[StackSize]; //栈数组 int top; //栈顶指针 } SeqStack; 栈的数组表示 — 顺序栈 0 1 2 3 4 5 6 7 8 9 StackSize-1 top (栈空) data
int Stack Empty(SeqStack *S)t //判断栈是否空?空则返回1.否则返回0 return S->to p int Stack Full(Seq Stack *S)& /判断栈是否满?满则返回1.否则返回0 return S->top= StackSize-1 void Initstack( SeqSstack*S){/置空栈 S->top=-1;
int StackEmpty (SeqStack *S) { //判断栈是否空？空则返回1，否则返回0 return S->top == -1; } int StackFull (SeqStack *S) { //判断栈是否满？满则返回1，否则返回0 return S->top == StackSize-1; } void InitStack ( SeqStack *S) { //置空栈 S->top = -1; }
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] //栈顶指针退到栈底