文档介绍：第三章栈和队列第三章栈和队列?教学时间:6学时?教学目的:? 1、理解栈的定义、特性,掌握栈的存储结构以及基本操作的实现;?2、理解队列的定义、特性,掌握队列的存储结构以及基本操作的实现;?教学内容:? 1、栈的定义、特点、两种存储结构、栈的应用?2、队列的定义、特点、两种存储结构、队列的应用课题5:栈的定义及存储表示?教学时间:2学时?教学目的:理解栈的定义、特性,掌握栈的存储结构以及基本操作的实现;?教学内容:栈的定义、特点、两种存储结构、栈的应用?教学重点:堆栈的概念;存储表示?教学难点:栈的运算?教学方法:讲授,投影?教学过程:?内容:?? ?后进先出? ? 1、顺序栈?栈的顺序存储表示?栈的基本操作? 2、链栈?? ? :栈的定义及存储表示?本章学****导读?从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。通过本章的学****读者应能掌握栈和队列的逻辑结构和存储结构,以及栈和队列的基本运算以及实现算法。 栈的定义?栈(stack)是限定在表尾一端进行插入或删除操作的线性表。在栈中,允许插入和删除操作的一端称为栈顶(top),而另一端称为栈底(bottom)。不含元素的栈称为空栈。?在栈的运算中,栈的插入操作称为进栈或入栈,栈的删除操作称为退栈或出栈。入栈出栈栈底栈顶入栈出栈( a ) 栈的示意图( b ) 铁路调度站表示栈a1a2ana4 入栈a3 出栈栈底bottom栈的示意图a3a2a1栈顶top根据栈的定义,每一次进栈的元素都在原栈顶元素之上,并成为新的栈顶元素;每一次出栈的元素总是当前的栈顶元素,因此最后进栈的元素总是最先出栈,所以栈也称为后进先出(Last In First Out)线性表,简称为LIFO表。课堂练****设3个元素进栈的先后顺序为A,B,C,试问能否得到出栈顺序:?(1)ABC (2)CBA (3)ACB?(4)BAC (5)BCA (6)CAB?推论:元素进栈的先后顺序为…i…j…k…,则不能得到的出栈顺序为:?…k…i…j…栈的抽象数据类型定义ADT Stack{数据对象:D={ai│ai∈ElemSet,i=1,2,…,n,n≥0}数据关系:R={〈ai-1,ai〉│ai-1,ai∈D,i=1,2,…,n}基本操作: InitStack(&S) DestroyStack(&S) ClearStack(&S) StackLength(S) GetTop(S,&e) Push(&S,e) Pop(&S,&e)……}ADT Stack栈的学****栈逻辑结构:线性结构——后进先出存储结构基本运算:出栈、入栈、取栈顶元素顺序存储:顺序栈链接存储:链式栈