资源描述：
《chap3堆栈与队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章栈和队列四类基本结构：1.线性结构2.树形结构3.图状结构4.集合1）线性表2）栈和队列3）串4）数组与广义表栈与队列的逻辑特征：从数据结构角度讲，栈与队列也是线性表，不同之处在于其操作的特殊性（栈为LIFO，队列为FIFO），为操作受限的线性表。从数据类型角度讲，栈与队列是与线性表不同的重要抽象数据类型，广泛的应用于各类软件系统中。3.1栈3.1.1栈的抽象类型定义3.1.2栈实现——顺序栈与链栈3.1.3栈的应用举例3.1.4栈与递归过程3.2队列3.2.1队列的类型定义3.2.2队列类型的实现3.2.3队列的应用举例3.1.1栈的抽象类型定
2、义栈顶(Top):允许进行插入、删除操作的一端栈底(Bottom):另一端，不允许插入、删除的一端空栈(StackEmpty):表中没有元素1.基本概念定义:作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。an...a2a1栈顶Top栈底Bottom栈s=(a1,a2,……,an)进栈:栈的插入操作,或称为入栈出栈:栈的删除操作,或称为退栈特点：后进先出(LIFO)LastInFirstOut1.基本概念an...a2a1栈顶Top栈底Bottom进栈出栈栈s=(a1,a2,……,an)元素入栈的顺序与出栈的顺序相反栈的抽象数据
3、类型定义ADTStack{数据对象：数据关系：基本操作：1.InitStack(&S)2.StackEmpty(S)3.Push(&S,x)4.Pop(&S,&x)5.GetTop(S,&x)}ADTStackR={
4、ai-1,ai∈D,i=2,3,...,n}约定an端为栈顶，a1端为栈底。D＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}…………了解各种操作的功能即可3.1.2栈的实现——顺序栈——链栈1.顺序栈#defineStack_Size初始分配量typedefstruct{StackElementType
6、elem[Stack_Size]；inttop；}SeqStack;(最简单、最常用)为栈分配一个足够大的容量。顺序栈toptoptoptoptoptopDABCE①顺序栈的初始化②顺序栈的判断栈是否为空③顺序栈的判断栈是否为满④顺序栈的入栈⑤顺序栈的出栈⑥顺序栈的取栈顶元素2.顺序栈的基本操作：voidInitStack(SeqStack*S){S->top=-1;}3.顺序栈的基本操作——初始化函数空栈top#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];intto
7、p；}SeqStack;intIsEmpty(SeqStackS){if(S.top==-1)returnTRUE;elsereturnFALSE;}3.顺序栈的基本操作——判断栈是否为空栈空top#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;intIsFull(SeqStackS){if(S.top==StackSize-1)returnTRUE;elsereturnFALSE;}3.顺序栈的基本操作——判断栈是否为满栈满topDA
8、BCE#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;intPush(SeqStack*S,ElemTypex){if(S->top==Stack_Size-1)returnFALSE;S->top++;S->elem[S->top]=x;returnTRUE;}3.顺序栈的基本操作——入栈入栈toptoptoptoptoptopDABCE#defineStack_Size50typedefstruct{StackElementType
9、elem[Stack_Size];inttop；}SeqStack;intPop(SeqStack*S,ElemType*x){if(S->top==-1)returnFALSE;*x=S->elem[S->top];S->top--;returnTRUE;}3.顺序栈的基本操作——出栈问题：栈顶top要修改吗？要修改，栈发生变化！！出栈toptoptoptoptoptopDABCE#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;3.顺
10、序栈的基本操作——取栈顶元素问题：栈顶top要修改吗？不要修改，栈没有变化！！取元素DABCE
