天津大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第三 章 栈和队列

第三章栈和队列 栈 令队列 令递归

❖ 栈 ❖ 队列 ❖ 递归 第三章栈和队列

栏( Stack) 定义是限定仅在表尾进行插入或删除操 作的线性表。 允许插入和删除的一端出栈进栈 称为栈顶(op),另一端 称为栈底 bottom) to 特点:后进先出LIFO bottom

栈 ( Stack ) ▪ 定义:是限定仅在表尾进行插入或删除操 作的线性表。 ▪ 允许插入和删除的一端 称为栈顶(top)，另一端 称为栈底(bottom) ▪ 特点：后进先出 (LIFO) a1 top bottom an . . . . 出栈 进栈

栈的主要操作 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 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 b b ase base ba ase 空栈 a进栈 b进栈

栈的表示和实现 ▪ 顺序栈：栈的顺序存储结构，利用一组地址连 续的存储单元依次存放自栈底到栈顶的数据元素， 指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 base 空栈 a 进栈 b 进栈 a a b top base top base top

top top top→ b base→a b base→a ba ase cba 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 100 #define stacKincrement 1o typedef char StackData; ypedef 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)t if(S->op=S->base) return1/判栈空空则返 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 x sizeof(stackData)); if(S->base)exit(OVERFLOW); S->top=S->base S->stacksize= STACK INIT SIZE Return oks

▪初始化 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)( /插入元素x为新的栈顶元素 if( StackFull(s)t S->base =( StackData*)malloc(S->base (S->stacksize+ STACKINCREMENT)* sizeof(StackData)); if( S->baseexit(overflow) S->top=S->base+S->stacksize S> stacksize+= 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)( /若栈空返回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; }