数据结构与算法第3章 栈和 队列.pptx

《数据结构与算法第3章 栈和 队列.pptx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、栈和队列是两种常用的数据类型栈是限定仅在表尾进行插入和删除的线性表。队列是限定仅在表尾进行插入、在表头进行删除的线性表。第3章限定性线性表——栈和队列123.1栈3.2队列3.3总结与提高本章作业与上机题目第3章限定性线性表——栈和队列33.1栈第3章限定性线性表——栈和队列3.1.1栈的定义3.1.2栈的表示和实现3.1.3栈的应用举例3.1.4栈与递归的实现返回4定义：作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈

2、。栈的插入操作被形象地称为进栈或入栈。栈的删除操作称为出栈或退栈。特点：后进先出（LIFO）进栈出栈示意图a1…a2an栈底栈顶3.1栈第3章限定性线性表——栈和队列练习题设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1234的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序。如入栈序列为123456,则能否得到出栈序列435612和13542653.1栈第3章限定性线性表——栈和队列6抽象数据类型：ADTStack{}ADTStack数据对象：D＝{ai

3、ai∈ElemSet,i=1,2,...

4、,n,n≥0}数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：1.InitStack（S）2.ClearStack（S）3.IsEmpty（S）4.IsFull（S）5.Push（S，x）6.Pop（S，x）7.GetTop（S，x）3.1栈第3章限定性线性表——栈和队列返回7①顺序栈②链栈3.1栈第3章限定性线性表——栈和队列8①顺序栈用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态

6、地指示栈顶元素在顺序栈中的位置。3.1栈第3章限定性线性表——栈和队列9顺序栈的C语言描述#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop;/*用来存放栈顶元素下标*/}SeqStack;ABCtoptoptoptopDtopEtoptop=-1表示空栈。3.1栈第3章限定性线性表——栈和队列10顺序栈的基本操作：①初始化②判栈空③判栈满④进栈⑤出栈⑥取栈顶元素3.1栈第3章限定性线性表——栈和队列11顺序栈的基本操作：①初始化voidInitStack(SeqSta

7、ck*S){S->top=-1;}#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;3.1栈第3章限定性线性表——栈和队列12顺序栈的基本操作：②判栈空intIsEmpty(SeqStack*S){return(S->top==-1?TRUE:FALSE);}#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;3.1栈第3章限定性线性表

8、——栈和队列13顺序栈的基本操作：③判栈满intIsFull(SeqStack*S){return(S->top==Stack_Size-1?TRUE:FALSE);}#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;3.1栈第3章限定性线性表——栈和队列14顺序栈的基本操作：④进栈intPush(SeqStack*S,StackElementTypex){if(S->top==Stack_Size-1)return(FALSE);S->top++

9、;S->elem[S->top]=x;return(TRUE);}#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;3.1栈第3章限定性线性表——栈和队列15顺序栈的基本操作：⑤出栈intPop(SeqStack*S,StackElementType*x){if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];S->top--;return(TRUE);}}#defineStack_Size50ty

10、pedefstruct{