第3章 堆栈和队列.ppt

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

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

3、转换任务。,5,例1：堆栈是什么？它与一般线性表有什么不同？,堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进”插入=压入,“出”删除=弹出,6,例2、一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,解：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入

4、，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的输出可以实现，每压入一数便立即弹出即可。,8,二、堆栈抽象数据类型,数据集合： a0, a1, , an-1 ai的数据类型为 DataType 操作集合：(1)StackInitiate(S) 初始化堆栈S (2)StackNotEmpty(S) 堆栈S非空否

5、(3)StackPush(S,x) 入栈 (4)StackPop(S,d) 出栈 (5)StackTop(S,d) 取栈顶数据元素 等,9,三、堆栈的顺序表示和实现,1、顺序（堆）栈 顺序存储结构的堆栈。 2、顺序栈的存储结构 它是利用一组地址连续的存储 单元依次存放自栈底到栈顶的数据元 素，同时设指针top指示栈顶元素的 当前位置。用C语言定义为： typedef struct DataType stackMaxStackSize; int top; SeqStack;,an,10,问：顺序表和顺序栈的操作有何区别？,写入：Si= ai 读出： e= Si,压入(PUSH): Stop+=a

6、n 弹出( POP) : e=S-top,an,以线性表 S= (a0 , a1 , . , an-2 , an-1)为例,前提：一定要预设栈顶指针top,11,栈不存在的条件： base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=MaxSize;,入栈口诀：堆栈指针top “先压后加” : Stop+=an 出栈口诀：堆栈指针top “先减后弹” : e=S-top,12,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。,下面用3个例子来帮助理解堆栈：,13

7、,void test(int *sum) int x; scanf(“%d”, ,断点地址入栈,例1、阅读下列递归过程，说明其功能。,输入x10,输入x50,输入x2,输入x3,输入x4,输出sum0,输出sum0+x4,输出sumx4+x3,输出sum x4+x3 +x2,输出sum x4+x3 +x2+x1,注意：最先输入的数据 x1 最后才被累加,程序功能：对键盘输入数据求和，直到输入0结束,14,例2、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,答：,43512不可能实现，主要是其中的12顺序不能实现； 12345的

8、输出可以实现，每压入一数便立即弹出即可。,思考：有无通用的判别原则？,15,例3、,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A）、D）可以， B）、C）不行。,讨论：有无通用的判别原则？ 有！若输入序列是 ,PjPkPi (PjPkPi) ，一定不存在这样的输出序列 ,PiPjPk ,答：,即对于输入序列1，2，3，不存在输出序列3，1，2,16,3、顺序栈的操作实现,(1)初始化栈 void StackInitiate(SeqStack *S)/*初始化顺序堆栈S*/ S-top = 0;

9、 /*定义初始栈顶下标值*/ ,17,(2)判栈非空否,int StackNotEmpty(SeqStack S) /*判顺序堆栈S非空否，非空则返回1，否则返回0*/ if(S.top = 0)return 0; else return 1; ,18,(3)入栈,int StackPush(SeqStack *S, DataType x) /*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0 */ if(S-top = MaxStackSize) printf(堆栈已满无法插入! n); return 0; else S-stackS-top = x; S-top +; retur

10、n 1; ,19,(4)出栈,int StackPop(SeqStack *S, DataType *d) /*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/ if(S-top top -; *d = S-stackS-top; return 1; ,20,(5)取栈顶数据元素,int StackTop(SeqStack S, DataType *d) /*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/ if(S.top = 0) printf(堆栈已空! n); return 0; else *d = S.stackS.top - 1;

11、return 1; ,21,例：用堆栈存放（A，B，C，D）,A,A,C B A,B A,顺序栈入栈函数的核心语句： S-stackS-top = x; S-top +;,低地址L,高地址M,B,C,D,22,例：从栈中取出B,顺序栈出栈函数的核心语句： S-top -; *d = S-stackS-top; 注：DataType *d； SeqStack *S；,23,四、堆栈的链式表示和实现,1、 链栈的存储结构 以头指针为栈顶，在头指针处插入或删除.,栈顶,栈底,栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈,链栈中每个结点由两个域构成： data域和next域，其定义为：,ty

12、pedef struct snode DataType data; struct snode * next; LSNode;,24,2、链式堆栈的操作实现,入栈 int StackPush(LSNode *head, DataType x) LSNode *p; if(p = (LSNode *)malloc(sizeof(LSNode) = NULL) printf(内存空间不足无法插入! n); return 0; p-data = x; p-next = head-next;/*新结点链入栈顶*/ head-next = p; /*新结点成为新的栈顶*/ return 1; ,25,(2

13、)出栈,int StackPop(LSNode *head, DataType *d) LSNode *p = head-next; if(p = NULL) printf(堆栈已空出错！); return 0; head-next = p-next;/*删除原栈顶结点*/ *d = p-data; /*原栈顶结点元素赋予d*/ free(p); /*释放原栈顶结点内存空间*/ return 1; 注： 由此可以看出：一个链栈由其栈顶指针唯一指定 设head指向栈顶元素，则head=NULL 表示栈空,26,在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。 一般不会出现栈满情况；除非没有空间导致malloc分配失败。 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。 采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,几点说明:,27,例1：括号匹配的检验 假设一个算法表达式中包含圆括号、方