第三章栈和队列 栈 令队列 令递归
❖ 栈 ❖ 队列 ❖ 递归 第三章栈和队列
栏( Stack 定义:是限定仅在表尾进行插入或删除操 作的线性表。 允许插入和删除的一端出栈进栈 称为栈顶op),另一端 称为栈底 ( bottom) op 特点:后进先出IFO) bottom- 1
栈 ( Stack ) ▪ 定义:是限定仅在表尾进行插入或删除操 作的线性表。 ▪ 允许插入和删除的一端 称为栈顶(top)，另一端 称为栈底(bottom) ▪ 特点：后进先出 (LIFO) a1 top bottom an . . . . 出栈 进栈
栈的主要操作 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); /判栈满否
栈的主要操作 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); //判栈满否 }
栈的表示和实现 顺序栈:栈的顺序存儲结构,利用一组地址连 续的存储单元依次存放自栈底到栈顶的数据元素, 指针top指向栈顶元素在顺序栈中的下一个位置, base为栈底指针,指向栈底的位置。 top top op base base→a base-人d 空栈 a进栈 b进栈
栈的表示和实现 ▪ 顺序栈：栈的顺序存储结构，利用一组地址连 续的存储单元依次存放自栈底到栈顶的数据元素， 指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 base 空栈 a 进栈 b 进栈 a a b top base top base top
top top elcba p d b base b base edcb base→a e进栈 ∫进栈溢出 e出栈
top top a b c d e e 进栈 a b c d e f 进栈溢出 a b d e 出栈 c base base base top
顺序栈的类型表示: #define stacK nit size 1oo #define stacKincrement 10 typedef char StackData typedef struct{顺序栈定义 StackData*base;/栈底指针 StackData *top;/栈顶指针 int stacksize;/当前已分配的存储空间 3 Seqstack
顺序栈的类型表示: #define STACK_INIT_SIZE 100； #define STACKINCREMENT 10； typedef char StackData; typedef struct { //顺序栈定义 StackData *base; //栈底指针 StackData *top; //栈顶指针 int stacksize；//当前已分配的存储空间 } SeqStack；
顺序栈的基本运算: 判栈空 int StackEmpty(SeqStack *S)i if(S->top==S->base) return1/判栈空,空则返 回1 else return0;/则返回0 判栈满 int StackFull(SeqStack *S)t if( s->top-S->base > s-> StackSize )return 1 /判栈满,满则返回1 else return0;/否则返回0
▪ 判栈空 int StackEmpty (SeqStack *S) { if( S->top == S->base ) return 1 //判栈空,空则返 回1 else return 0; //否则返回0 } ▪ 判栈满 int StackFull (SeqStack *S) { if( S->top- S->base >= S-> StackSize ) return 1 //判栈满,满则返回1 else return 0; //否则返回0 } 顺序栈的基本运算:
初始化 void initstack( Seqstack*S){/置空栈 S->base=( StackData*)malloc(STACK INIT SIZE sizeof(StackData)); if(s->base)exit(OVERFLOW); S-top= S->base S->stacksize= STACK INIT SIZE Return ok;
▪初始化 void InitStack ( SeqStack *S) { //置空栈 S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW); S->top = S->base ; S->stacksize= STACK_INIT_SIZE ; Return ok; }
入栈 int Push(Seqstack"S, StackData x)i /插入元素x为新的栈顶元素 if( Stack Full(s)) S->base=( StackData*)malloc(S->base (S->stacksize+ STACKINCREMENT)X sizeof(StackData) if(! S-> base)exit(overflow) S->top=S->base +S->stacksize S-> estacksize+= STACKINCREMENT;/追加存储空间 S->top)=x; (S->top)++ Return ok
▪ 入栈 int Push (SeqStack *S, StackData x) { //插入元素x为新的栈顶元素 if ( StackFull (S) ){ S->base =( StackData *)malloc(S->base , (S->stacksize+ STACKINCREMENT) * sizeof(StackData)); if(! S->base)exit(overflow); S->top= S->base + S->stacksize; S->stacksize+= STACKINCREMENT; //追加存储空间 } *(S->top)=x; （S->top）++; Return ok }
取栈顶元素 int Gettop (Seqstack*S, StackData &x)i /若栈空返回0,否则栈顶元素读到x并返回1 if( StackEmpty(s)) return 0; (S->top) X=*(S->top); return 1
▪ 取栈顶元素 int Gettop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; (S->top)--; x = *(S->top); return 1; }