资源描述：
《数据结构资料ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章栈和队列1通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型23.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列——队列的链式表示和实现3.3.3循环队列——队列的顺序表示和实现33.1栈3.1
2、.1抽象数据类型栈的定义1、栈(Stack)的定义栈是限定仅在表尾进行插入和删除操作的线性表。术语栈底(bottom)——栈的表头栈顶(top)——栈的表尾空栈——没有元素的栈入栈(push)——向栈顶压入元素出栈(pop)——从栈顶弹出元素anan-1...a2a1栈底栈顶入栈出栈栈的特点栈的修改是按后进先出的原则进行的。因此，栈称为后进先出的线性表（LIFO）。43.1.1抽象数据类型栈的定义2、栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。DCBAABCDDC
3、BA53.1.1抽象数据类型栈的定义2、栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ABCDE操作序列：出栈序列：①元素A入栈AA②元素B入栈BB③元素C入栈CC63.1.1抽象数据类型栈的定义2、栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈B
4、③元素C入栈④元素C出栈CC⑤元素B出栈B73.1.1抽象数据类型栈的定义2、栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈DD⑦元素D出栈D⑧元素A出栈A83.1.1抽象数据类型栈的定义2、栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列
5、A、B、C、D、E得到出栈序列CBDAE？E操作序列：出栈序列：①元素A入栈②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈⑦元素D出栈D⑧元素A出栈A⑨元素E入栈EE⑩元素E出栈E9请大家思考如下问题结合书上图3.1（b）铁路调度站示意图，如果有编号分别为1，2，3，4的四列火车顺序开过来，如果你是调度，有多少种出站顺序？分别是什么？14种出站顺序1234、1243、1324、1342、1432、2134、2143、2314、2341、2431、3214、3241、3421、4321推广到一般情
6、况：10例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。435612中到了12顺序不能实现；135426可以实现。例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：答：11例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性
7、来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。123.1.1抽象数据类型栈的定义3、栈的抽象数据类型定义ADTStack{数据对象：D＝{ai
8、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
9、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack
10、13InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTraverse(S,visit())14InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果
