资源描述：
《数据结构C语言第3章 栈和 队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、DataStructure第三章栈和队列100865107/22/20211学习目标掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。熟练掌握栈类型的两种实现方法。熟练掌握循环队列和链队列的基本操作实现算法。理解递归算法执行过程中栈的状态变化过程。重点和难点栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点是掌握这两种结构的特点，以便能在应用问题中正确使用。知识点顺序栈、链栈、循环队列、链队列7/22/20212栈和队列是在程序设计中被广泛使用的两种线性数据结构。与线性表相比，它们的插入和删除
2、操作受更多的约束和限定，故又称为限定性的线性表结构。线性表允许在表内任一位置进行插入和删除；栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删除。7/22/202133.1栈栈限定只能在表的一端进行插入和删除操作的线性表。栈顶(top)：允许插入和删除的一端。栈底(bottom)：不允许插入和删除的另一端。空栈：不含元素的空表。（a1,a2,……,an）栈顶栈底7/22/20214a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图特点先进后出（FILO）后进先出（LIF
3、O）7/22/20215例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈底栈顶ab栈顶c栈顶情况1：7/22/20216栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况1：栈的逻辑结构7/22/20217栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构7/22/2
4、0218栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况2：栈的逻辑结构还有其他情况吗？7/22/20219栈的抽象数据类型定义ADTStack{数据对象：D＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}基本操作：InitStack(&S)操作
7、结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。 操作结果：栈S被销毁。7/22/202110ClearStack(&S)初始条件：栈S已存在。 操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。 操作结果：返回栈S中元素个数，即栈的长度。7/22/202111GetTop(S,&e)初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：
8、栈S已存在。 操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。7/22/202112StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问 函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack7/22/202113栈的顺序存储（顺序栈）利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。结构定义：#defineSTACK_IN
9、IT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//存储空间基址SElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素位单位}SqStack;7/22/202114top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组大小为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满
10、，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空进栈：top加1出栈：top减17/22/202115基本操作接口(函数声明)voidInitStac
