第3章 栈与队列 数据结构ppt课件.ppt

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

1、第三章堆栈和队列3.1堆栈（Stack）基本概念、抽象数据类型、顺序表示和实现、链式表示和实现3.2堆栈应用括号匹配问题3.3队列（Queue）基本概念、抽象数据类型、顺序队列、顺序循环队列、链式队列、队列的应用11.定义一堆栈（stack）与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。4.存储结构5.运算规则6.实现方式3.逻辑结构限定只能在表的一端进行插入和删除操作的线性表。

2、1.1基本概念2.特点后进先出。2在栈满时还进行入栈运算，必定会产生空间的溢出7、栈“下溢”6、栈“上溢”当栈空时仍进行出栈运算，必定会产生空间的溢出。3定义：栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈S=(a０,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务

3、。1.2堆栈(stack)定义4a0a1an-1入栈出栈栈顶top栈底bottom栈的示意图．．．下面是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。1.3堆栈(stack)的结构图例1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入“出”＝删

4、除=弹出6例2、一个栈的输入序列为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种可能性。7例3、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？解：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数

5、便立即弹出即可。8例4、设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA）、D）可以，B）、C）不行。讨论：有无通用的判别原则？有！若输入序列是…,Pj…Pk…Pi…(Pj

6、y(S)堆栈S非空否(3)StackPush(S,x)入栈(4)StackPop(S,d)出栈(5)StackTop(S,d)取栈顶数据元素等101.5堆栈的顺序表示和实现顺序栈的存储结构它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。用C语言定义为：#defineMAXNUM<最大元素数>typedefstruct{DataTypestack[MAXNUM];inttop;}SeqStack;鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。a0a1

7、……an-1顺序栈Sai……an栈底base栈顶top11a0a1……an-1顺序栈Sai……问：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an弹出(POP):e=S[--top]低地址高地址S[i]a0a1aian-1……顺序表S……an以线性表S=(a0,a1,….,an-2,an-1)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top12栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=MaxSize;a0a1…

8、…an-1顺序栈Sai…