第3章_堆栈和队列ppt课件.ppt

《第3章_堆栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.1堆栈3.2栈应用典型题例3.3栈与递归的实现3.4队列3.5队列应用典型题例3.6实训例题第3章堆栈和队列3.1.1堆栈的定义及基本运算堆栈简称为栈，是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作“栈顶”，另一端称作“栈底”。通常将元素插入栈顶的操称作为“入栈”（进栈或压栈），称删除栈顶元素的操作为“出栈”）表。栈底栈顶入栈出栈图3.1堆栈a1a2an…3.1堆栈3.1堆栈(2)堆栈的基本运算如下。(1)StackInit()初始化堆栈。(2)StackEmpty(s)判定栈s是否为空。(

2、3)StackLength(s)求堆栈s的长度。(4)GetTop(s)获取栈顶元素的值。(5)Push(s,e)将元素e进栈。(6)Pop(s)，出栈（删除栈顶元素）。3.1.2堆栈的顺序存储结构#defineMaxSize堆栈可能达到的最大长度typedefstruct{ElementTypeelem[MaxSize];inttop;　　　　/*栈顶位置*/}SeqStack;3.1堆栈(3)(1)初始化堆栈StackInit()SeqStackStackInit(SeqStack*s){s.top=-1;return(s)

3、;}/*StackInit*/(2)判定栈s是否为空StackEmpty(s)intStackEmpty(SeqStacks){return(s.top==-1);}/*StackEmpty*/(3)求堆栈s的长度StackLength(s)intStackLength(SeqStacks){return(s.top+1);}/*StackLength*/3.1堆栈(4)(4)获取栈顶元素的值GetTop(s)ElementTypeGetTop(SeqStacks){if(StackEmpty(S))/*空栈*/return(n

4、il);return(s.elem[s.top]);}/*GetTop*/(5)进栈Push(s,e)voidPush(SeqStack*s,ElementTypee){if(S->top==MaxSize-1)/*栈满*/printf(“Full”);else{s->top++;s->elem[s->top]=e;}}/*Push*/3.1堆栈(5)(6)出栈Pop(s)ElementTypePop(SeqStack*s){if(S->top==-1)/*栈空*/return(nil);/*返回空值*/else{e=s->el

5、em[s->top];s->top--;return(e);}}/*Pop*/3.1堆栈(6)【例1】假设有两个栈共享一个一维数组空间[0,MaxSize－1]，其中一个栈用数组的第0单元（元素）作为栈底，另一栈用数组的第MaxSize－1号单元（元素）作为栈底（即两个堆栈从两端向中间延伸），其对应的类型描述如下：#defineMaxSize堆栈可能达到的最大长度typedefstruct{ElementTypeelem[MaxSize];inttop1,top2;　　　　/*栈顶位置*/}ShareStack;试写出共享栈的进

6、栈、出栈算法。3.1堆栈(7)则栈1的栈顶表示为:s->top1，栈2的栈顶表示为:s->top2;栈1的进栈操作使得栈顶1右（后）移，即s->top1++，栈2进栈操作使得栈顶2左（前）移，即s->top1--;栈满时两个栈顶相邻，即s->top1+1＝＝s->top2。图3.2共享堆栈栈1栈顶2a1anb1bm栈2栈底1栈底20…MaxSize-1栈顶13.1堆栈(8)voidPush(ShareStack*s,ElementTypee,inti)/*将元素e压入栈i(i=1,2)*/{if(s->top1+1＝＝s->to

7、p2)/*栈满*/printf(“Full”);else{if(i==1){s->top1++;s->elem[s->top1]=e;}else{s->top2--;s->elem[s->top2]=e;}}}/*Push*/3.1堆栈(9)ElementTypePop(ShareStack*s,inti)/*栈i(i=1,2)出栈*/{if(i==1)if(s->top1==-1)/*栈1空*/return(nil);else{e=s->elem[s->top1];s->top1--;return(e);}if(i==2)if

8、(s->top2==MaxSize)/*栈2空*/return(nil);else{e=s->elem[s->top2];s->top2++;return(e);}}/*Pop*/3.1堆栈(10)3.1.3栈的链式存储结构链栈的类型描述如下：typedefst