第三章 堆栈

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.1,堆栈（,Stack,）,基本概念、抽象数据类型,顺序表示和实现,链式表示和实现,3.2,堆栈应用,括号匹配问题,3.3,队列（,Queue,）,基本概念、抽象数据类型,顺序队列、顺序循环队列、链式队列、队列的应用,第三章 堆栈和队列,1,一、堆栈的基本概念,定义：,只能在表的,一端,进行插入和删除操作的线性表。,特点：, 逻辑结构与线性表相同，为,一比一,（,1:1,）关系。, 堆栈中允许进行插入和删除数据元素的一端为栈顶，另一端称为栈底。, 插入元素到栈顶的操作称为,进栈,或入栈，从栈顶删除元素的操作通常称为,出栈,或退栈。, 堆栈中的数据元素实行,后进先出,或先进后出。,2,存储结构：,用,顺序栈,或,链栈,存储均可，但以顺序栈更常见。,栈“上溢”：,在栈满时还进行入栈运算,栈“下溢”：,当栈空时仍进行出栈运算,3,栈,是仅在表尾进行插入、删除操作的线性表。,表尾,(,即,a,n,端,),称为栈顶,/top ;,表头,(,即,a,1,端,),称为栈底,/base,例如： 栈,S,= (,a, a,2 ,a,3 , .,a,n-1 ,a,n,),a,n,称为栈顶元素,a,1,称为栈底元素,强调：,插入和删除都只能在表的一 端（栈顶）进行！,4,例,1,、,一个栈的输入序列为,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,种可能性。,5,例,2,、,一个栈的输入序列是,12345,，若在,入栈的过程中允许出栈,，,则栈的输出序列,43512,可能实现吗？,12345,的输出呢？,解：,43512,不可能实现，主要是其中的,12,顺序不能实现；,12345,的输出可以实现，每压入一数便立即弹出即可。,6,例,1,：堆栈是什么？它与一般线性表有什么不同？,堆栈是一种特殊的线性表，它只能在表的,一端（即栈顶）,进行插入和删除运算。,与一般线性表的区别：仅在于,运算规则,不同。,一般线性表,堆栈,逻辑结构：,1:1,逻辑结构：,1:1,存储结构：顺序,表,、链,表,存储结构：顺序栈、链栈,运算规则：,随机存取,运算规则：,后进先出,(LIFO),“进”插入,=,压入,“,出”删除,=,弹出,7,数据集合：, a,0, a,1, , a,n-1,a,i,的数据类型为,DataType,操作集合,：,(1)StackInitiate(S),初始化堆栈,S,(2)StackNotEmpty(S),堆栈,S,非空否,(3)StackPush(S,x),入,栈,(4)StackPop(S,d),出栈,(5)StackTop(S,d),取栈顶数据元素,一、堆栈抽象数据类型,8,二、堆栈的顺序表示和实现,1,、顺序（堆）栈,顺序存储结构的堆栈。,2,、顺序栈的存储结构,它是利用一组地址连续的存储,单元依次存放自栈底到栈顶的数据,元素，同时设指针,top,指示,当前栈顶,位置,。,a,0,a,1,a,n-1,顺序栈,S,a,i,a,n,栈底,base,栈顶,top,9,3,、,C,语言描述：,typedef,struct,DataType,stackMaxStackSize,;,int,top;,SeqStack,;,10,a,0,a,1,a,n-1,顺序栈,S,a,i,问：顺序表和顺序栈的操作有何区别？,表头,表尾,低地址,高地址,写入：,Si=,a,i,读出：,e= Si,压入,(,PUSH),:,S,top+,=a,n,弹出,(,POP),:,e=S,-top,低地址,高地址,Si,a,0,a,1,a,i,a,n-1,顺序表,S,a,n,以线性表,S,= (a,0, a,1 , . ,a,n-2 ,a,n-1,),为例,栈底,base,栈顶,top,前提：一定要,预设,栈顶指针,top,栈顶,top,11,栈不存在的条件：,base=NULL;,栈为空的条件,：,base=top;,topstackS-top = x;,S-top +;,top,top,top,top,低,地址,L,高地址,M,B,C,D,13,例：从栈中取出,B,D,C,B,A,top,top,D,C,A,B,D,C,B,A,top,D,C,B,A,top,低,地址,L,高地址,M,D,顺序栈出栈函数的核心语句：,S-top -;,*d = S-stackS-top;,注：,DataType,*d,；,SeqStack,*S,；,14,例,2,、,设依次进入一个栈的元素序列为,c,，,a,，,b,，,d,，,则可得到出栈的元素序列是：,）,a,，,b,，,c,，,d,）,c,，,d,，,a,，,b,）,b,，,c,，,d,，,a,）,a,，,c,，,d,，,b,A,）、,D,）,可以，,B,）、,C,）,不行。,讨论：有无通用的判别原则？,有！,若输入序列是,P,j,P,k,P,i,(,P,j,P,k,top = 0; /*,定义初始栈顶下标值*,/,16,(2),判栈非空否,int,StackNotEmpty(SeqStack,S),/*,判顺序堆栈,S,非空否，非空则返回,1,，否则返回,0*/,if(S.top top =,MaxStackSize,),printf,(,堆栈已满无法插入,! n);,return 0;,else ,S-stackS-top = x;,S-top +;,return 1; ,18,(4),出栈,int,StackPop(SeqStack,*S,DataType,*d),/*,弹出顺序堆栈,S,的栈顶数据元素值到参数,d,，,出栈成功则返回,1,，否则返回,0*/,if(S,-top top -;,*d = S-stackS-top;,return 1; ,19,(5),取栈顶数据元素,int,StackTop(SeqStack,S,DataType,*d),/*,取顺序堆栈,S,的当前栈顶数据元素值到参数,d,，,成功则返回,1,，否则返回,0*/, if(S.top data = x;,p-next = head-next;/*,新结点链入栈顶*,/,head-next = p; /*,新结点成为新的栈顶*,/,return 1;,22,(2),出栈,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;,注：,由此可以看出：一个链栈由其,栈顶指针唯一指定,23,在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，,可,不设头结点,链栈。,一般,不会出现栈满,情况；除非没有空间导致,malloc,分配失败。,链栈的入栈、出栈操作就是栈顶的插入与删除操作，,修改指针即可完成,。,采用链栈存储方式的优点是，可使,多个栈共享空间,；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,几点说明,:,24,例,1,：,括号匹配的检验,假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数。,设计思路：用栈暂存左括号,3.2,栈的应用举例,25,void,ExpIsCorrect(char,exp,int,n),/,判断有,n,个字符的字符串,exp,左右括号是否配对正确,SeqStack,myStack,;,int,i;char c;,StackInitiate(&myStack,);,for(i=0;in;i+),if(expi=()|(expi= )|(expi= ),StackPush(&myStack, expi);,else if(expi = ) &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c = (),StackPop(&myStack, ,26,else if(expi = ) &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c != (),printf,(,左右括号配对次序不正确！,n);,return;, else if(expi = &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c = ),StackPop(&myStack, ,else if(expi = &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c != ),printf,(,左右括号配对次序不正确！,n);,return;,27,else if(expi = &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c = ),StackPop(&myStack, ,else if(expi = &,StackNotEmpty(myStack,),&,StackTop(myStack, &c) & c != ),printf,(,左右括号配对次序不正确！,n);,return;,.,28,