数据结构教学课件：第03章_栈和队列A

1、第三章：栈和队列第三章：栈和队列1 13.1栈栈 (Stack) 3.2 队列队列 (Queue) 第三章：栈和队列第三章：栈和队列2 21. 基本概念基本概念2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 基本概念基本概念2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 定义定义: 限定只能在表的进行插入和删除运算的线性表。 3 3与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)关系。关系。用用或或存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在运算，且访问结点时依照运算，且访问

2、结点时依照（LIFOLIFO）或）或（FILOFILO）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。序栈或链栈的存储结构有别而不同。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构即栈顶即栈顶基本操作有：基本操作有：建栈、判断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。读栈顶元素值，等等。 是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 /top ; 表头表头(即即 a1 端端)称

3、为称为栈底栈底/base例如：例如： 栈栈 = (a1 , a2 , a3 , .,an-1 , an )插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！4 4a1a2an入栈入栈出栈出栈栈顶栈顶 top栈底栈底 bottom栈的示意图栈的示意图例例1（严题集3.1）一个栈的输入序列为一个栈的输入序列为1,2,3，若在，若在入栈的过程中允许出栈入栈的过程

4、中允许出栈，则可能得到的出栈序列是，则可能得到的出栈序列是什么？什么？5 5可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种

5、可能性。种可能性。例例2：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则则可得到出栈的元素序列是：可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b6 6解答解答 A）、）、D）可以，）可以， B）、）、C）不行。）不行。讨论：有无通用的判别原则？讨论：有无通用的判别原则？即对于输入序列即对于输入序列1，2，3，不存在输出序列，不存在输出序列3，1，2有！若输入序列是有！若输入序列是 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kP=S.stacksize)/栈满，追加存储空间 S.base=(SEle

6、mType*) realloc (S.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /先推元素入栈顶，然后栈顶指针自增 return OK;/push 3.1 3.1 栈栈1515ABCtopbasePop (&S, &e) S.top-;e = *S.top;e = Ce = CABtopbasePop(&

7、;S, &e) S.Top-; e = *S.top;e = Be = BAtopbaseS.top -;e = *S.top;Pop(&S, &e) e = Ae = A( (教材教材p.47)p.47)3.1 3.1 栈栈1616Status Pop(SqStack &S, SElemType &e) /若栈不为空，则删除S的栈顶元素，用e返回其值， / 并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop 3.1 3.1 栈栈1717(1) 链栈的构造方式链

8、栈的构造方式以头指针为栈顶，以头指针为栈顶，在头指针处在头指针处插入或删除插入或删除.Node *st, *p;int m=sizeof(Node); 栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈栈顶栈顶栈底栈底 a1 a2an-1 annextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedef Struct SNode SElemType data; Struct SNode * next; Node;1)1) 链栈链栈不必设头结点不

9、必设头结点，因为栈顶（表头）操作频繁；，因为栈顶（表头）操作频繁；2)2) 链栈一般链栈一般不会出现栈满不会出现栈满情况，除非没有空间导致情况，除非没有空间导致malloc( )malloc( )分配失败。分配失败。3)3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成修改指针即可完成。4)4) 采用链栈存储方式的优点是，可使采用链栈存储方式的优点是，可使多个栈共享空间多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。链栈是栈的首选存储方式。几点说明

10、几点说明:3.1 3.1 栈栈1818Push (SElemType e) p=(Node*)malloc(m); if(!p)上溢上溢 else p-data=e; p-link=st; st=p; Status Pop( ) if(st=NULL)下溢下溢 elsee=st-data;p=st;st=st-link; free(p); return(e); 插入插入表头表头从表头从表头删除删除由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针唯一指定。栈顶指针唯一指定。 设设指向栈顶元素，当指向栈顶元素，当=NULL=NULL时表示栈空时表示栈空3.1 3.1 栈栈1919Q4Q

11、4：为什么要设计栈？它有什么实际用途？：为什么要设计栈？它有什么实际用途？20201.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题。简化了程序设计的问题。【例例】 编写算法，用栈实现表达式编写算法，用栈实现表达式求值。求值。(表达式求值表达式求值是栈应用的典型例子是栈应用的典型例子, , 参见参见( (教材教材p.52)p.52) 注：本例采用注：本例采用 “算符优先法算符优先法”。 一个算术表达式是由一个算术表达式是由操作数操作数（x，y，z）和）和算符算符（* ，

12、/， + ，-，（，），（，），# ）组成）组成.教材教材P53P53中表中表3.13.1给出了算符之间的优先级给出了算符之间的优先级表达式的表达式的起止符号起止符号 a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外输入计算机的表达式为：输入计算机的表达式为： # 3*（7 2 ）#21211）首先让表达式的起始符）首先让表达式的起始符 为为的栈底元素，并置的栈底元素，并置为空栈为空栈 ；2）依次读入表达式中的每个字符，）依次读入表达式中的每个字符，若运算符是若运算符是# #且栈顶是且栈顶是# #，则结束计算，返回，则结束计算，返回栈顶

13、值。栈顶值。 if（是操作数）（是操作数） 则则PUSH（ ，操作数）；，操作数）； if（是运算符）（是运算符） 则与则与栈顶元素进行比较，按优先级栈顶元素进行比较，按优先级( (详见详见P53P53表表3.13.1的规定）的规定）进行操作；进行操作；为了实现算符优先算法，可以设定两个工作栈：为了实现算符优先算法，可以设定两个工作栈：存放运算符号，存放运算符号， 存放操作数或运算结果存放操作数或运算结果 。3）直到整个表达式求值完毕（当前读入的字符和）直到整个表达式求值完毕（当前读入的字符和栈的栈顶元素均为栈的栈顶元素均为 ）if栈顶元素栈顶元素 运算符运算符，则退栈、按栈顶计算，将结果压入

14、则退栈、按栈顶计算，将结果压入栈。栈。且该未入栈的运算符要保留，继续与下一个栈顶元素比较！且该未入栈的运算符要保留，继续与下一个栈顶元素比较！o operatorperator & operand & operand2222表达式求值过程表达式求值过程 机内运算示意图机内运算示意图3.1 3.1 栈栈2323OPTROPNDINPUT# 3 *（7 2 ）#遇到右括号时，开始执行教材遇到右括号时，开始执行教材P54最上面的最上面的case 语句部分：语句部分：Pop(OPTR, theta); theta =-Pop(OPND, b); b = 2Pop(OPND, a); a

15、 = 7Push(OPND, Operate(a, theta, b); Operate(a,theta,b)=7-2 = 5 OPND 372topbase#*(-topbase35topbase表达式求值过程的描述：表达式求值过程的描述：OPTROPNDINPUTOPERATE3*(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

16、, 2)#Operate(7-2)#, *, (3, 5)#Pop(optr)#, *3, 5#Operate(3*5)#15#GetTop(opnd)# 3 *（7 2 ）#程序见程序见P53P532424Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#)|(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar(); else switch(p

17、recede(GetTop(OPTR) , c) case : Pop(OPTR ,theta); Pop(OPND,b);a=Pop();thetabreak; /switch /while result=GetTop(OPND);/EvaluateExpression 栈顶与运算符比栈顶与运算符比较并查表较并查表3.13.1判判C C是否是否操作符操作符2525算法算法3.43.4，教材，教材p.47p.47问：问：教材教材P53P53表表3.13.1中，中， 1 1和和 2 2哪个对应栈顶元素，哪哪个对应栈顶元素，哪个对应键盘输入值？个对应键盘输入值？答：答：根据根据P53 Preced

18、e()P53 Precede()函数可知，函数可知， 1 1对应栈顶元素对应栈顶元素由表由表3.1可看出，右括号可看出，右括号 ) 和井号和井号 # 作为作为 2时时级别最低；级别最低；由由c 规则规则得出：得出： * ，/， + ，-为为 1时的优先权低于时的优先权低于，高于高于由由a规则规则得出：得出：= 表明括号内的运算已完成；表明括号内的运算已完成； = 表明表达式求值完毕。表明表达式求值完毕。2626【例例】写出下面写出下面C程序段的执行结果。程序段的执行结果。运行结果为：运行结果为： 5 5，120120long int fact(int n) long f; if(n1) f=n

19、*fact(n-1); else f=1; return(f); main int n; long y; n=5; y=fact(n); printf(“%d,%ldn”,n,y); 什么叫递归？什么叫递归？3.1 3.1 栈栈2727递归模型：递归模型：递归模型由递归出口和递归体组成，前者指出递归终止的条件，后者指出递归中的递推关系。例如，计算阶乘n!的递归模型如下： f(n)=1 n=1 f(n)=nf(n-1)n1递归算法设计：递归算法设计：递归算法设计一般的过程是先求出递归模型，然后转换成递归算法。求递归模型的一般步骤如下：1. 对原问题f(s)进行分析，假设出合理的“较小问题”f(s

20、)2. 假设f(s)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s)之间的关系。3. 确定一个特殊的情况(如f(1)或f(0)的解，由此作为递归出口)。3.1 3.1 栈栈2828编制递归算法要注意些什么？编制递归算法要注意些什么？ 递归进行是有条件的。一般常把判断语句加在递归语句以前。递归进行是有条件的。一般常把判断语句加在递归语句以前。3.1 3.1 栈栈2929递归的最底层应该有返回值，以供上层递归的调用。否则会递归的最底层应该有返回值，以供上层递归的调用。否则会死循环。死循环。递归调用需要利用递归调用需要利用堆栈堆栈。参量的初始化应该在递归以前。参量的初始化应该在递归以前

21、。每次调用要把本次调用的参数和局部变量保存在栈顶。每次调用要把本次调用的参数和局部变量保存在栈顶。每次从下一层调用返回到上一层调用时，从栈顶恢复本层调每次从下一层调用返回到上一层调用时，从栈顶恢复本层调用的参数和局部变量的值。用的参数和局部变量的值。void test(int &sum) int x; scanf(x); if(x=0) sum=0; else ; sum+=x; printf(sum);【例例】（严题集严题集3.103.10）阅读下列递归过程，说明其功能。阅读下列递归过程，说明其功能。注意：注意：最先最先输入的数据输入的数据 x1最后才被最后才被累加累加程序功能：对键盘输入数据程序功能：对键盘输入数据求和，直到输入求和，直到输入0 0结束结束3.1 3.1 栈栈3030输入输入x50输入输入x10输入输入x2输入输入x3输入输入x4输出输出sum0输出输出sum0+x4输出输出sumx4+x3输出输出sum x4+x3 +x2输出输出sum x4+x3 +x2+x1断点地址断点地址入栈入栈【例例】递归应用递归应用汉诺（汉诺（ HanoiHanoi）塔问题）塔问题传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小