资源描述：
《第3章 堆栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、3.1堆栈（Stack）基本概念、抽象数据类型、顺序表示和实现、链式表示和实现3.2堆栈应用括号匹配问题3.3队列（Queue）基本概念、抽象数据类型、顺序队列、顺序循环队列、链式队列、队列的应用第三章堆栈和队列11.定义一、堆栈的基本概念与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。3.存储结构4.运算规则5.实现方式
2、2.逻辑结构限定只能在表的一端进行插入和删除操作的线性表。特点：后进先出。基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等。2在栈满时还进行入栈运算，必定会产生空 间的溢出7、栈“下溢”6、栈“上溢”当栈空时仍进行出栈运算，必定会产生空间的溢出。3栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈S=(a０,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为
3、栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。4例1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=压入“出”＝删除=弹出5例2、一个栈
4、的输入序列为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种可能性。6例3、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？解：43512不可能实现，主要是其中的12顺序不能实现
5、；12345的输出可以实现，每压入一数便立即弹出即可。7二、堆栈抽象数据类型数据集合：{a0,a1,…,an-1｝ai的数据类型为DataType操作集合：(1)StackInitiate(S)初始化堆栈S(2)StackNotEmpty(S)堆栈S非空否(3)StackPush(S,x)入栈(4)StackPop(S,d)出栈(5)StackTop(S,d)取栈顶数据元素等8三、堆栈的顺序表示和实现1、顺序（堆）栈顺序存储结构的堆栈。2、顺序栈的存储结构它是利用一组地址连续的存储单元依次存放自栈底到栈
6、顶的数据元素，同时设指针top指示栈顶元素的当前位置。用C语言定义为：typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;a0a1……an-1顺序栈Sai……an栈底base栈顶top9a0a1……an-1顺序栈Sai……问：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an弹出(POP):e=S[--top]低地址高地址S[i]a0a1aian-1……顺序表S
7、……an以线性表S=(a0,a1,….,an-2,an-1)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top10栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=MaxSize;a0a1……an-1顺序栈Sai……低地址高地址an栈底base栈顶top入栈口诀：堆栈指针top“先压后加”:S[top++]=an出栈口诀：堆栈指针top“先减后弹”:e=S[--top]11问：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递
8、归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。下面用3个例子来帮助理解堆栈：12voidtest(int*sum){intx;scanf(“%d”,&x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}断点地址入栈例1、阅读下列递归过程，说明其功能。输入x1≠0输入x5＝0输入x2输入x3输入x4输出sum＝0输出sum＝0+x4输出sum＝x4+x3输出sum＝x4+
