数据结构课件(第3章)栈和队列

《数据结构课件(第3章)栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列信阳师范学院计算机与信息技术学院第三章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列2021/6/122信阳师范学院计算机与信息技术学院基本内容：栈的抽象数据类型定义（逻辑结构）；栈的两类存储结构及基本操作实现的算法；栈在程序设计中的应用。学习要点：掌握栈“后进先出”的特征并灵活运用；重点掌握顺序栈的各种操作实现。理解递归算法执行过程中栈的作用及栈的状态变化2021/6/123信阳师范学院计算机与信息技术学院（1）栈和队列的基本概念。（2）栈和队列的顺序存储结构。（3）栈和队列的链式存储结构。（4）栈和队列的应用。考研大纲要求及分析1考纲要求2

2、021/6/124数据结构考研辅导本章是必考内容，出题形式主要以选择题为主。对于栈，常考的一类题目是考查栈的后进先出特性，例如给定一个入栈序列，判断某个出栈序列的合法性（或不合法性），共享栈也是一个常考点。对于队列，循环队列是一个常考点，注意队空、队满的判定条件，队列长度的计算。由于栈和队列的算法比较简单，通常水会单独以算法设计题的形式出题，在树和图的算法设计中，栈和队列通常作为辅助数据结构，因此，需要熟练掌握栈和队列的基本操作语句。2考纲分析2021/6/125数据结构考研辅导a1a2a3……an入栈栈底栈顶出栈栈的示意图栈的特点后进先出第一个进栈的元素在栈底，最后一个进栈

3、的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素3.1栈3.1.1抽象数据类型栈的定义栈（stack）是一种后进先出（lastinfirstout,LIFO）的线性表，限定仅能在表尾一端进行插入和删除操作。2021/6/126信阳师范学院计算机与信息技术学院ADTStack{数据对象:D={ai

4、aiElemSet,i=1,2,…，n,n>=0}数据关系:R1={

5、ai-1,aiD,i=2,…，n}约定其中a1端为栈底，an端为栈顶。基本操作：……}//ADTStack建栈、入栈、出栈、判断栈空等，教材中列出了9种基本操作。抽象数据类型

6、栈的定义2021/6/127信阳师范学院计算机与信息技术学院1） 初始化操作InitStack((&S)功能：构造一个空栈S；2）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈;3）置空栈操作ClearStack(&S)功能：将栈S置为空栈;4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回;5）进栈操作Push(&S,e)功能：元素e进栈;6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回;7）判空操作StackEmpty(S)功能：若栈S为空，则返回True，否则返回False;出栈进栈栈的基本操作栈的示意图栈顶栈底an

7、a2a12021/6/128信阳师范学院计算机与信息技术学院栈操作图示topbaseAtop（4）EDC出栈（1）空栈（2）A进栈（3）BCDE进栈BCDEtoptoptoptop2021/6/129信阳师范学院计算机与信息技术学院栈与一般线性表有什么不同？栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)202

8、1/6/1210信阳师范学院计算机与信息技术学院一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：①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种可能性。例2（严题集3.1）2021/6/1211信阳师范学院计算机与信息技术学院一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43

9、512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。例3：2021/6/1212信阳师范学院计算机与信息技术学院栈的顺序存储结构是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。----顺序栈3.1.2栈的顺序存储和实现2021/6/1213信阳师范学院计算机与信息技术学院#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT10//栈存储空间