第三章栈和队列 栈( 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; }