数据结构第三章栈教材课件

数据结构课程的内容数据结构课程的内容13.1 栈（栈（Stack）3.2 队列队列（Queue）第三章第三章 栈和队列栈和队列1.1.定义定义2.2.逻辑结构逻辑结构3.3.存储结构存储结构4.4.运算规则运算规则5.5.实现方式实现方式1.1.定义定义2.2.逻辑结构逻辑结构3.3.存储结构存储结构4.4.运算规则运算规则5.5.实现方式实现方式21.定义定义:3.1 栈栈与线性表相同，仍为一对一与线性表相同，仍为一对一(1:1)关系关系。用用顺序栈顺序栈顺序栈顺序栈或或链栈链栈链栈链栈存储均可，但以顺序栈更存储均可，但以顺序栈更常见常见只能在只能在栈顶栈顶栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进后进后进后进先出先出先出先出（LIFOLIFO）或或先进后出先进后出先进后出先进后出（FILOFILO）的原则。的原则。关键是编写关键是编写入栈入栈入栈入栈和和出栈出栈出栈出栈函数，具体实现依函数，具体实现依顺序栈或链栈的存储结构有别而不同。顺序栈或链栈的存储结构有别而不同。3.存储结构存储结构:4.运算规则运算规则:5.实现方式实现方式:2.逻辑结构逻辑结构:限定只能在表的限定只能在表的一端一端一端一端进行插入和删除运进行插入和删除运算的线性表。算的线性表。即栈顶即栈顶基本操作有：基本操作有：建栈、判断栈满或栈空、入栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。出栈、读栈顶元素值，等等。3栈栈栈栈 是仅在表尾进行插入、删除操作的线性表。是仅在表尾进行插入、删除操作的线性表。表尾表尾(即即 a an n 端端)称为称为栈顶栈顶 /top;/top;表头表头(即即 a a1 1 端端)称为称为栈底栈底/base/base例如：例如：栈栈 S S S S=(=(a a1 1 ,a ,a2 ,2 ,a a3 ,.,3 ,.,a an-1 ,n-1 ,a an n)插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素想一想：要从栈中取出想一想：要从栈中取出想一想：要从栈中取出想一想：要从栈中取出a1，应当如何操作？应当如何操作？应当如何操作？应当如何操作？强调：强调：强调：强调：插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！4Q1Q1：堆栈是什么？它与一般线性表有什么不同？堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的堆栈是一种特殊的线性表，它只能在表的一端（即一端（即栈顶）栈顶）进行插入和删除运算。进行插入和删除运算。与一般线性表的区别：仅在于与一般线性表的区别：仅在于运算规则运算规则运算规则运算规则不同。不同。一般线性表一般线性表一般线性表一般线性表 堆栈堆栈堆栈堆栈逻辑结构：逻辑结构：1:1 逻辑结构：逻辑结构：1:1 存储结构：顺序表、链表存储结构：顺序表、链表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：运算规则：随机存取随机存取随机存取随机存取 运算规则：运算规则：后进先出后进先出后进先出后进先出(LIFO)“进进”插入插入=压入压入=PUSH=PUSH（a an+1n+1)“出出”删除删除=弹出弹出=POP=POP(a(an n)5 a1 a2 an顺序栈顺序栈S aiQ2Q2：顺序表和顺序栈的操作有何区别？顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si=ai读出：读出：e=Si压入压入(PUSH)PUSH):SStoptoptoptop+=an+1弹出弹出(POP)POP):e e=S=S-toptoptoptop 低地址低地址高地址高地址Si a1 a2 ai an 顺序表顺序表S an+1以线性表以线性表 S=(a1 ,a2 ,.,an-1,an)为例为例栈底栈底basebase栈顶栈顶toptop前提：一定要前提：一定要预设预设预设预设栈顶指针栈顶指针toptoptoptop栈顶栈顶toptop6栈不存在的条件：栈不存在的条件：base=NULL;base=NULL;栈为空的条件栈为空的条件 ：base=top;base=top;栈满的条件栈满的条件 ：top-base=top-base=stacksizestacksize;a1 a2 an顺序栈顺序栈S ai低地址低地址高地址高地址 an+1栈底栈底basebase栈顶栈顶toptop7向上生成向上生成：若入栈动作使地址向高端增长；：若入栈动作使地址向高端增长；向下生成向下生成：若入栈动作使地址向低端增长；：若入栈动作使地址向低端增长；Q3Q3：什么叫什么叫“向上生成向上生成”的栈？的栈？“向下生成向下生成”又是何又是何意？意？答：答：对于向上生成的堆栈对于向上生成的堆栈:入栈口诀：入栈口诀：堆栈指针堆栈指针top“top“先压后加先压后加”:出栈口诀：出栈口诀：堆栈指针堆栈指针top“top“先减后弹先减后弹”:e=S-tope=S-topStop+=aStop+=an+1n+18Q4Q4：为什么要设计堆栈？它有什么独特用途？为什么要设计堆栈？它有什么独特用途？1.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题简化了程序设计的问题。下面用下面用4 4个例子来帮助理解堆栈：个例子来帮助理解堆栈：答：答：9void test(int&sum)int x;scanf(x);if(x=0)sum=0;elsetesttest(sumsum);sum+=x;printf(sum);断点地址断点地址入栈入栈例例1 1（严题集严题集3.103.10）阅读下列递归过程，说明其功能。阅读下列递归过程，说明其功能。输入输入x10输入输入x50输入输入x2输入输入x3输入输入x4输出输出sum0输出输出sum0+x4输出输出sumx4+x3输出输出sum x4+x3+x2输出输出sum x4+x3+x2+x1注意：最先注意：最先输入的数据输入的数据 x x1 1 最后才被最后才被累加累加程序功能：对键盘输入数据求程序功能：对键盘输入数据求和，直到输入和，直到输入0 0结束结束10例例2:2:一个栈的输入序列为一个栈的输入序列为1,2,31,2,3，若在，若在入栈的过程入栈的过程中允许出栈中允许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？答：答：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1 1入入1 1出，出，2 2入入2 2出，出，3 3入入3 3出，出，即即 ；123123132132231231213213321321 1 1入入1 1出，出，2 2、3 3入，入，3 3、2 2出，出，即即 ；1 1、2 2入，入，2 2出，出，3 3入入3 3出，出，即即 ；1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出，即即 ；1 1、2 2、3 3入，入，3 3、2 2、1 1出，出，即即 ；合计有合计有5 5种可能性。种可能性。11例例3 3：一个栈的输入序列是一个栈的输入序列是1234512345，若在，若在入栈的过程入栈的过程中允许出栈中允许出栈，则栈的输出序列则栈的输出序列4351243512可能实现吗？可能实现吗？答：答：4351243512思考：有无通用思考：有无通用的判别原则？的判别原则？1234512345的输出呢？的输出呢？不可能实现不可能实现主要是其中的主要是其中的1212顺序不能实现顺序不能实现1234512345可以实现可以实现每压入一数便立即弹出即可。每压入一数便立即弹出即可。12例例4 4：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c c，a a，b b，d d，则则可得到出栈的元素序列是：可得到出栈的元素序列是：）a a，b b，c c，d d ）c c，d d，a a，b b ）b b，c c，d d，a a ）a a，c c，d d，b b B）、）、C）讨论：有无通用的判别原则？讨论：有无通用的判别原则？有！若输入序列是有！若输入序列是 ,P,Pj jPPk kPPi i(P(Pj jPPk kPstacksize)if(top-Lstacksize)追追加加存储空间存储空间 else s else stop+top+=e;=e;Push(B);Push(C);Push(D);toptoptoptop低低地址地址LPush(A);高地址高地址MBCD18顺序栈出栈操作顺序栈出栈操作例如从栈中取出例如从栈中取出B B B BDCBAtoptopDCABDCBAtopDCBAtop低低地址地址L高地址高地址MD核心语句：核心语句：Pop();顺序栈出栈函数顺序栈出栈函数 Pop()Pop()status Pop()status Pop()if(top=L)if(top=L)下溢下溢 else e=selse e=s-top-top;return(e);return(e);Pop();Printf(Pop();19链栈的入栈操作和出栈操作链栈的入栈操作和出栈操作（教材省略）（教材省略）(1)(1)链栈的构造方式链栈的构造方式以头指针为栈顶，以头指针为栈顶，在头指针在头指针 处处插入或删除插入或删除.Node *st,*p;int m=sizeof(Node);栈顶栈顶栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈st st a a1 1 a a2 2a an-1n-1 a an nnextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedef Struct SNode SElemType data;Struct SNode *next;Node;20Push(SElemType e)p=(Node*)malloc(m);if(!p)上溢上溢else p-data=e;p-next=st;st=p;Status Pop()if(st=NULL)下溢下溢elsee=st-data;p=st;st=st-next;free(p);return(e);链栈链栈入栈入栈函数函数链栈链栈出栈出栈函数函数插入插入表头表头从表头从表头删除删除(2)(2)操作操作由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针唯一指定栈顶指针唯一指定 设设stststst指向栈顶元素，则指向栈顶元素，则 stststst =NULL =NULL 表示栈空表示栈空211)1)链栈链栈不必设头结点不必设头结点，因为栈顶（表头）操作频，因为栈顶（表头）操作频繁；繁；2)2)链栈一般链栈一般不会出现栈满不会出现栈满情况，除非没有空间导情况，除非没有空间导致致mallocmalloc分配失败。分配失败。3)3)链栈的入栈、出栈操作就是栈顶的插入与删除链栈的入栈、出栈操作就是栈顶的插入与删除操作，操作，修改指针即可完成修改指针即可完成。4)4)采用链栈存储方式的优点是，可使采用链栈存储方式的优点是，可使多个栈共享多个栈共享空间空间；当栈中元素个数变化较大，且存在多个；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。栈的情况下，链栈是栈的首选存储方式。几点说明几点说明:22栈的应用栈的应用-过程的嵌套调用过程的嵌套调用r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程323例例1:1:数制转换（十转数制转换（十转N N）P48P48 设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例2 2：括号匹配的检验：括号匹配的检验P49P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例3 3：表达式求值表达式求值 P52P52 设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例4 4：汉诺仪（汉诺仪（HanoiHanoi）塔）塔P55P55 设计思路：用栈实现递归调用设计思路：用栈实现递归调用24例例1:1:数制转换数制转换 例例 把十进制数把十进制数159159转换成八进制数转换成八进制数(159)10=(237)815981982802 3 7 余余 7余余 3余余 2toptop7top73top72325Void conversion()InitStack(S);/构造空栈构造空栈 scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(“%d”,e);/conversion26例例2:2:括号匹配的检验括号匹配的检验 假设一个算术表达式中包含圆括弧、方假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数别表达式中括弧是否正确配对的函数correct(exp,tag)correct(exp,tag)；其中：其中：expexp为字符串类为字符串类型的变量（可理解为每个字符占用一个数组型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，元素），表示被判别的表达式，tagtag为布尔为布尔型变量。型变量。27算法的设计思想：算法的设计思想：1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空 若栈空，则表明该若栈空，则表明该“右括弧右括弧”多余多余 否则和栈顶元素比较，否则和栈顶元素比较，若相匹配，则若相匹配，则“左括弧出栈左括弧出栈”否则表明不匹配否则表明不匹配3）表达式检验结束时，）表达式检验结束时，若栈空，则表明表达式中匹配正确若栈空，则表明表达式中匹配正确 否则表明否则表明“左括弧左括弧”有余有余28Status matching(string&exp)int state=1;initstack(s);while(i=Length(exp)&state)switch of expi case 左括弧:Push(S,expi);i+;break;case”)”:if(NOT StackEmpty(S)&GetTop(S)=“(“)Pop(S,e);i+;else state=0;break;if(StackEmpty(S)&state)return OK;.29例例3:3:行行编辑程序编辑程序功能功能:接受用户从终端输入的程序或数据，并存接受用户从终端输入的程序或数据，并存入用户的数据区。入用户的数据区。思路思路:设立一个输入缓冲区，接受用户输入的一设立一个输入缓冲区，接受用户输入的一行字符，然后逐行存入用户数据区。允许用户出行字符，然后逐行存入用户数据区。允许用户出错，并在发现有误时可以及时更正。错，并在发现有误时可以及时更正。举例举例:#:#:表示前一个字符无效；表示前一个字符无效；：表示当前行中的字符均无效。表示当前行中的字符均无效。Whli#ilr#e(sWhli#ilr#e(s#*s)#*s)outchaputcharoutchaputchar(*s=#+);(*s=#+);While(*s)While(*s)putcharputchar(*s+);(*s+);30Void LineEdit()InitStack(S);/构造空栈构造空栈S S ch=getchar();/从终端接收第一个字符从终端接收第一个字符 while(ch!=EOF)/EOF/EOF为全文结束符为全文结束符 while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,C);break;/仅当栈非空时退栈仅当栈非空时退栈 case:ClearStack(S);break;/重置重置S S为空栈为空栈 default:Push(S,ch)break;/有效字符进栈，未考虑栈满情形有效字符进栈，未考虑栈满情形31 ch=getchar();/从终端接收下一个字符从终端接收下一个字符 /将从栈底到栈顶的栈内字符传送至调用过程的数据区将从栈底到栈顶的栈内字符传送至调用过程的数据区 ClearStack(S);/重置重置S S为空栈为空栈 if(ch!=EOF)ch=getchar();DestroyStack(S);/LineEdit32例例4 4 表达式求值表达式求值 (这是栈应用的典型例这是栈应用的典型例子子 )这里，这里，表达式求值的算法是表达式求值的算法是“算符优先法算符优先法”.例如：例如：3*3*（7 2 7 2）（1 1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则：a.a.从左算到右从左算到右 b.b.先乘除，后加减先乘除，后加减 c.c.先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为：3*3*（7 2 7 2）=3*5=15=3*5=1533（2 2）根据上述三条运算规则，在运算的每一步）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符中，对任意相继出现的算符 1 1和和 2 2 ，都要比较优都要比较优先权关系先权关系算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53P53表表3.13.1（是提供给计算机用的表！）（是提供给计算机用的表！）由表可看出，右括号由表可看出，右括号 )和井号和井号#作为作为 2 2时时级别级别最低；由最低；由c c 规则规则得出：得出：*，/，+，-为为 1 1时的时的优先权低于优先权低于（，高于，高于）由由a a规则规则得出：得出：（=）表明括号内运表明括号内运算，已算完。算，已算完。#=#表明表达式表明表达式求值完毕。求值完毕。34（3 3）算法思想：）算法思想：设定两栈：设定两栈：操作符栈操作符栈 OPTR OPTR，操作数栈操作数栈 OPNDOPND栈初始化：栈初始化：设操作数栈设操作数栈 OPND OPND 为空；操作符栈为空；操作符栈 OPTR OPTR 的栈底元素为表达式起始符的栈底元素为表达式起始符#；依次读入字符依次读入字符：是操作数则入：是操作数则入OPNDOPND栈，栈，是操作符则是操作符则要判断：要判断：if if 操作符操作符 栈顶元素栈顶元素，压入，压入OPTROPTR栈。栈。35OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3)#*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)36Status EvaluateExpression(OperandType&result)InitStack(OPND);Push(OPTR,#);InitStack(OPTR);c=getchar();while(c!=#)&(GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();/不是运算符则进栈不是运算符则进栈 else栈的应用（表达式求值）算法描述栈的应用（表达式求值）算法描述37 switch(Precede(GetTop(OPTR),C)case :/栈顶元素优先权低栈顶元素优先权低 Push(OPTR,c);c=getchar();break;case=:/脱括号并接收下一字符脱括号并接收下一字符 Pop(OPTR,x);c=getchar();break;case 1length 1），试写出其入栈、出栈操作），试写出其入栈、出栈操作的算法。的算法。393、写出下列程序段的输出结果（栈的元素类型写出下列程序段的输出结果（栈的元素类型SElemSElem Type Type为为charchar）。）。void main()Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);while(!StackEmpty(S)Pop(S,y);printf(y);Printf(x);404.4.设一循环队列设一循环队列QueueQueue，只有头指针只有头指针frontfront，不设尾指针，另设一个内含元素个数的计数不设尾指针，另设一个内含元素个数的计数器，试写出相应的入队、出队算法。器，试写出相应的入队、出队算法。5.5.设计一算法能判断一个算术表达式中的圆设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行括号配对是否正确。（提示：对表达式进行扫描，凡遇到扫描，凡遇到“（”就进栈，遇到就进栈，遇到“）”就就退出栈顶的退出栈顶的“（”，表达式扫描完毕时栈若，表达式扫描完毕时栈若为空则圆括号配对正确。）为空则圆括号配对正确。）返回41