资源描述：
《第3章栈和队列new》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章栈和队列【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。课前索引1第三章栈和队列【重点和难点】栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点及其实现，以便能在应用问题中正确使用。【知识点】顺序栈、链栈、循环队列、链队列课前索引2第三章栈和队列【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和
2、队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。课前索引3第三章栈和队列【课前思考】1.什么是线性结构？有何特点？2.农村存放粮食的粮栈在存、取粮食时有何特点？3.我们平时排队买票时，买票的次序有何特点？课前索引4第三章栈和队列栈和队列是在程序设计中被广泛使
3、用的两种特殊的线性表，它们的特殊性在于对栈和队列的插入和删除操作被限制为只能在表的两端进行：L=（a1,a2,a3,…,ai,…,an）线性表：在表的任意位置进行插入和删除：栈：只能在表尾进行插入和删除：“后进先出”。队列:只能在表尾进行插入,而在表头删除：“先进先出”。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为操作受限（或限定性）的线性表结构。5可将线性表和栈及队列的插入和删除操作对比如下：线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1//表尾//表
4、尾Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n//表尾//表头栈和队列是两种常用的数据类型63.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现第三章栈和队列73.1栈的类型定义一、栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表。表尾—栈顶，表头—栈底,不含元素的空表称空栈。特点：后进先出（LIFO）或先进后出（FILO）s=(a1,a2,……,an)ana1a2……...栈底栈顶...入栈出栈栈结构示意图8栈在日常生活中的实例：火车进出站圆柱筒子弹夹
5、9二、栈的类型定义ADTStack{数据对象：D＝{ai
6、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
7、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：……}ADTStack10InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())三、栈的基本操作：11InitSt
8、ack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。12StackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。13GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。14Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新
9、的栈顶元素。a1a2ane……15Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……163.2栈类型的实现顺序栈--栈的顺序存储表示链栈--栈的链式存储表示17top=0123450栈空栈顶指针top,指向栈顶元素的下一个空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢top=M,栈满，此时入栈，则上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空类似于线性表的
10、顺序映象实现，可用一维数组实现，定义指向表尾的指针可以作为栈顶指针。一维数组s[M]一、顺序栈类型的定义a1…an01……n-118㈠、用一维数组实现顺序栈的C语言描述#defineMaxlen100//顺
