第3章 栈和队列.ppt

1、CH3 栈和队列,教学内容： 本章介绍应用广泛的数据结构 栈(stack)和队列(queue)，将分别给出这两种结构的定义、基本运算、存储结构以及一些基本运算的具体实现，并给出一些应用实例。 教学重点与难点 重点是掌握栈和队列在两种存储结构上实现的基本运算 难点是应用栈解决一些实际问题，以及循环队列中对边界条件的处理。,教学目标 掌握栈和队列这两种数据结构的特点，了解在什么问题中应该使用哪种结构。 熟悉几个关系： 栈（队列）和线性表的关系； 顺序栈（顺序队列）和顺序表的关系； 链栈（链队列）和链表的关系。 重点掌握在顺序栈和链栈上实现的栈的七种基本运算，特别注意栈满和栈空的条件及它们的描述。

2、重点掌握在循环队列和链队列上实现的七种基本运算，特别注意队满和队空的描述方法。 熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上溢的原因；循环队列消除假上溢的方法。,3.1 栈,栈的定义 栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表。通常称允许插入、删除这一端为栈顶（top），另一端称为栈底(bottom)。 栈的修改是按后进先出的原则进行的，故又称栈为LIFO表(Last In First Out)。 栈的特征 栈的逻辑结构和我们先前学过的线性表相同。 栈的运算规则与线性表相比有更多的限制。,3.1.1 栈的抽象数据类型定义,ADT Stack 数据对象：D=ai|aiEl

3、emSet;1in,n0; 数据关系：R=| ai,ai+1D,i=1,2,n-1 基本操作： InitStack( ElemType *top; int stacksize; SqStack;,.基本操作的算法表示 初始化一个空栈 判栈空 取栈顶元素 入栈 出栈,1)初始化一个空栈,Status InitStack(SqStack ,2)取栈顶元素和元素出栈,Status GetTop(SqStack S,ElemType ,3)元素入栈,Status Push(SqStack ,思考题：,一个栈的入栈序列为：1 2 3，那么可能得到的出栈序列是什么？ 答：3 2 1，2 3 1，2 1 3

4、 ，1 3 2 ，1 2 3。 2.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何？ (2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。,3.1.3 栈的共享存储单元,引言 思考：两个栈如何共享存储空间？,“底设两端、相向而动、迎面增长”,3.1.4 链

5、栈的表示和实现,1.栈的链式存储表示 typedef struct SNode ElemType data; struct SNode *next; SNode,*LinkStack; 问： 链栈中为何不设置头结点? 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的首指针就可以了。,3.链栈基本操作的实现 初始化 S=NULL； 入栈 申请结点p； p-data=e; p-next=S; S=p; 判空： S=NULL 出栈： if (S=NULL) return ERROR; else p=S;

6、S=p-next; e=p-data; free(p); ,练习,(1)栈是限定在_处进行插入或删除操作的线性表。 A. 端点 B. 栈底 C. 栈顶 D. 中间 (2)4个元素按A、B、C、D顺序连续进S栈， 进行Pop(S,x)运算后，x的值是_。 A.A B. B C. C D. D (3)栈的特点是_。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不进不出,(4)栈与一般线性表的区别主要在_方面。 A. 元素个数 B. 元素类型 C. 逻辑结构 D. 插入、删除元素的位置 (5) 一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是_。 A. 2，3，4

7、，1，5， B. 5，4，1，3，2， C. 2，3，1，4，5， D. 1，5，4，3，2,3. 2 栈的应用举例,3.2.1 数制转换 void conversion() InitStack(S); scanf( %d , ,将除8的余数依次入栈S，先得的余数为低位，后得的余数为高位。,从栈顶到栈底元素依次出栈，得到对应的8进制数,3. 2 栈的应用举例,3.2.2 括号匹配的检查 例如： （） （ ） （ ） （ ） （）,算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否

8、则表明不匹配 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,Status Compare( ) InitStack(S); flag=TURE; while （ch= getchar( )）！=#） ,3.2.3 迷宫求解,求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。,求迷宫中一条从入口到出口的路径的算法： 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位

9、置的东邻方块为新的当前位置； 否则 while (栈不空）；,3.2.4 表达式求值,运算规则 实现思想 设置两个工作栈 运算符栈 操作数栈 算法描述,运算规则,OperandType Evaluateexpress() InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar( ); while (c!=# | GetTop(OPTR)!=#) if （c为操作数） Push(OPND,c);c=getchar(); else switch Precede(GetTop(OPTR),c) case :Pop(OPTR,theta);P

10、op(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; /switch /while / Evaluateexpress,有关思考与提示 算符优先表的存储和表示; 栈的选择（静态顺序栈-用数组表示） 判断c是否为算符。 Operate(a,theta,b) 的实现,Int change(char c) Switch c of case +:i=0;break; case -:i=1;break; case *:i=2;break; case /:i=3;break; case (:i=4;break; case ):i=5;bre

11、ak; case #:i=6;break; Return i; ,Char Precede(char c1,char c2) Char a77=, , , ,= i=change(c1);j=change(c2); Return aij ,课堂提问： 栈是什么？它与一般线性表有什么不同？ 堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：线性结构 逻辑结构：线性结构 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进”插入=入栈,“出”删除=出栈,3

12、.3 栈与递归的实现,一、函数调用与返回 通常，当一个函数调用另一个函数时，在执行被调用函数前系统要预先做三件事情： 将所有的实参和函数返回地址等信息传递给被调用函数； 为被调用函数的局部变量分配存储空间 将控制转移到被调用函数的入口处。,而在从被调用函数返回调用函数之前，系统也需要做如下三件事情： 保存被调用函数的计算结果； 释放为被调用函数局部变量分配的数据空间； 按返回地址将控制转移给调用函数。,二、函数的嵌套调用 当多个函数构成嵌套调用时，系统按照先调用后返回的原则进行工作。 这种信息的传递和控制转移符合后进先出的原则，使用栈来实现是非常自然的。 例： 设有一个主程序，它调用函数a，函

13、数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）,注： 系统将整个程序运行期间所需要的存储空间都利用一个工作栈来管理，每当调用（或执行）一个函数时，就为它在栈顶分配一个存储区； 每当退出（或执行完）一个函数时，就释放为它所分配的存储区； 当前工作的函数的数据区总在工作栈的当前栈顶位置。,三、递归函数的执行过程 递归函数的执行过程类似于嵌套调用时的情况，只不过是在直接递归时的调用函数和被调用函数是同一个函数罢了 递归是程序设计中一个强有力的工具，可以解决许多实际应用问题： 递归定义的数学函数 递归的数据结构 问题的定义是递

14、归的,3.3.1 递归的定义与实现,1. 很多数学函数的定义是递归的。 例：阶乘的定义和实现。,long fact(long n) if (n=0) return 1; else return n*fact(n-1); ,例如：,fact(4),2.递归的数据结构 例1：线性链表结构 打印非空链表f的最后一个结点的数据值 void find (Linklist f) if (f-next=NULL) printf(f-data); else find(f-next); 例2：树型结构,3.问题的解法是递归的,例：Hanoi塔问题 分析：,将X轴上的n1个盘子借助Z轴移到Y轴上； 将X轴上的余下

15、的1个盘子移到Z轴上； 将Y轴上的n1个盘子借助X轴移到Z轴上,求解算法及调用示意图,void hanoi(int n,char x,char y,char z) if (n=1) move (x,1,z); else hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); ,2.递归工作栈 目的：保证递归函数正确执行，系统设立工作栈作为递归函数运行期间使用的数据存储区。 内容： 函数返回地址 本次调用时与形参结合的实参 本层的局部变量值,3.3.2 递归过程与递归工作栈,递归算法的优点和缺点 利用递归算法（函数、过程、子程序等）编写的程序具有结构简洁

16、清晰、易读易理解等优点。 然而由于使用栈来实现这种“调用返回”的递归过程，无论在时间上还是在空间上都比相应的非递归程序的开销要大。,3.4 队列,队列的定义 队列(Queue)是仅限制在表的一端进行插入，另一端进行删除运算的线性表。通常称允许插入一端为队尾（rear），另一端称为队头(front)。 队列的修改是按先进先出的原则进行的，故又称栈为FIFO表(Fast In First Out)。,例如： 到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。 乘坐公共汽车，应该在车站排队，车来后，按顺序上车。 在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用

17、户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。,3.4.1 队列的抽象数据类型定义,ADT Queue 数据对象：D=ai|aiElemSet;1in,n0; 数据关系：R=| ai,ai+1D,i=1,2,n-1， 约定a1端为队列头，an端为队列尾 基本操作： InitQueue( struct Qnode *next; Qnode,*QueuePtr; typedef struct QueuePtr front； QueuePtr rear;

18、 LinkQueue 带头结点的链队列示意图：,1. 队列的初始化,Status InitQueue(LinkQueue ,2. 队列的销毁,Status DestroyQueue(LinkQueue ,3. 入队列,Status EnQueue(LinkQueue 说明： 所谓入队列即在队尾之后插入一个新结点，并让新结点成为新的队列尾.,4. 出队列,Status DeQueue(LinkQueue 注意：p指向被删除结点，需要考虑p是否为队尾结点指针。,5. 取队首,Status GetHead(LinkQueue Q, ElemType ,3.4.3 队列顺序存储的表示和实现,顺序队列的

19、特点 设立两棵指针Q.front和 Q.rear 队空的判定条件:Q.front= Q.rear 队满的判定条件:Q.rearQ.Maxsize,队列的顺序存储结构,存储结构定义 #define MAXQSIZE 100 typedef struct ElemType *base; int front; int rear; SqQueue;,顺序队列的“溢出”问题 (1)真溢出 Q.rear Q.front Q.Maxsize (2)假溢出 顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。,问题： 如何解决顺序队列的“假溢出”问题？ 答： 按最大可能的进队操作次数设置顺

20、序队列的最大元素个数； 修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置； 修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后方完成入队操作。 采用循环队列；,循环队列,1.基本思想 2.示意图,顺序队列,J1,J2,J3,Q.front,Q.rear,6 5 4 3 2 1 0,循环队列,一个新问题： 在循环队列中，队空特征是Q.frontQ.rear；队满时也会有Q.frontQ.rear ；判决条件将出现二义性！ 解决方案有三： 使用一个计数器记录队列中元素个数（即队列长度）； 判队满：countMAXQSIZE 判队空：count=0,加设标志位 判队满：tag=1 ,循环队列,2.入队列 Status EnQueue(SqQueue ,3.出队列 Status DeQueue(SqQueue ,3.5 队列应用,1.判断一个字符序列是否是回文。 基本思想： 将输入字符逐个分别存入队列和栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符