第三章栈和队列

1,数据结构课程的内容,2,3.1栈（Stack）,第三章栈和队列,3.2队列（Queue）,定义运算规则逻辑结构存储结构5.实现方式,定义运算规则逻辑结构存储结构5.实现方式,3,1.定义,3.1栈,限定只能在表的一端进行插入和删除运算的线性表,4,栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶top;表头(即a1端)称为栈底base,例如：栈s=(a1,a2,a3,.,an-1,an),a1称为栈底元素an称为栈顶元素,插入元素到栈顶（即表尾）的操作，称为入栈。从栈顶（即表尾）删除最后一个元素的操作，称为出栈。,教材P44对栈有更详细定义：,5,3.1栈,2.运算规则,根据定义，若给定栈s=(a1,a2,.,an)，且an为栈顶元素，欲加入新元素，则只能加在an的顶上作为栈顶元素；此时若要删除，则先删除栈顶元素。显然，栈的这种后进先出性是栈结构的特征，称栈为后进先出（LIFO表）或先进后出（FILO）的线性表。,由此得出：栈与一般线性表的区别仅在于运算规则不同。,6,3.1栈,与线性表相同，仍为一对一关系。,3.逻辑结构,栈是一种对所有插入、删除操作仅限于在表的一端进行的线性表，是一种后进先出型结构。栈和链表是两种不同的数据结构。,判断对错：,栈是逻辑结构的概念，是特殊的线性表，而链表是存储结构概念，二者不是同类项。,7,3.1栈,4.存储结构,用顺序存储或链式存储均可，分别称为顺序栈和链栈，但以顺序栈更常见。,5.实现方式,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。基本操作有读栈顶元素值、建栈、入栈、出栈、或判断栈满、栈空等。,8,顺序栈示意图,top,9,顺序栈定义typedefstructSElemType*base;SElemType*top;intstacksize;/当前可使用的最大容量SqStack;,栈不存在的条件：s.base=NULL;栈为空的条件：s.base=s.top;栈满的条件：s.top-s.base=s.stacksize;,10,表和栈的操作区别对于s=(a1,a2,.,an-1,an),写入：vi=ai读出：x=vi,入栈：PUSH(an+1)出栈：POP(x),前提：一定要预设栈顶指针top！,an+1,11,入栈操作例如用栈存放（A，B，C，D）（注意要遵循“后进先出”原则）,A,核心语句：s.top=s.base;,顺序栈中的PUSH函数statusPush(SqStackS，SElemTypee)if(s.top-s.base=s.stacksize)上溢else*S.top+=e;,Push(s,B);,Push(s,C);,Push(s,D);,低地址L,Push(s,A);,高地址M,B,C,D,12,出栈操作例如从栈中取出B（注意要遵循“后进先出”原则）,核心语句：Pop(s,e);Pop(s,e);Pop(s,e)Printf(e);,顺序栈中的POP函数statusPop(SqStackS，SElemTypee)if(s.top=s.base)空栈elsee=*-s.top;returnOK;,13,补：若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的栈入栈口诀：堆栈指针top先压后加（*s.top+=e）；出栈口诀：堆栈指针top先减后弹（e=*-s.top)。,3.1栈,14,例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。,答：,例1：在作进栈运算时应先判别栈是否_(1)_；在作出栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。,答：(1)满(2)空(3)n,15,例3一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解：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种可能性。,16,例4：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：）a，b，c，d）c，d，a，b）b，c，d，a）a，c，d，b,A、D可以（B、C不行）。,答：,规律：若借助栈由输入序列1，2，n得到输出序列为p1,p2,pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着ijk，使得pjlink=st;st=p;,链栈入栈函数,插入表头,20,if(st=NULL)栈空elsee=st-data;p=st;st=st-link;free(p);,链栈出栈函数,从表头删除,21,链栈不必设头结点，因为栈顶（表头）操作频繁；采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,说明,22,补：共享空间栈,例1：当两个栈共享一存储区时，栈利用一维数组sn表示，两栈顶指针为top1与top2，则当栈1空时，top1为_，栈2空时，top2为_，栈满时为_。例2：多个栈共存时，最好用_作为存储结构。,为了增加顺序栈内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的栈底分别设在内存空间的两端，这样只有当两栈顶指针相邻时才产生溢出。,top1+1=top2,0,n-1,链式存储结构,23,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。,答：,24,数制转换（十转N）P48设计思路：用栈暂存低位值例2：括号匹配的检验P49设计思路：用栈暂存左括号例3：表达式求值-P52设计思路：用栈暂存运算符例4：汉诺仪（Hanoi）塔-P55设计思路：用栈实现递归调用,例1：,25,例3表达式求值(这是栈应用的典型例子)这里，表达式求值的算法是“算符优先法”。,例如：3*（72）（1）要正确求值，首先了解算术四则运算的规则：a.从左算到右b.先乘除，后加减c.先括号内，后括号外由此，此表达式的计算顺序为：3*（72）=3*5=15,26,（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2，都要比较优先权关系。算符优先法所依据的算符间的优先关系见教材P53表3.1（是提供给计算机用的表！）由表可看出，右括号)和井号#作为2时级别最低；由c规则得出：*，/，+，-为1时的优先权低于（，高于）由a规则得出：（=）表明括号内运算，已算完。#=#表明表达式求值完毕。,栈的应用（表达式求值）,27,（3）算法思想：设定两栈：操作符栈OPTR，操作数栈OPND栈初始化：设操作数栈OPND为空；操作符栈OPTR的栈底元素为表达式起始符#；依次读入字符：是操作数则入OPND栈，是操作符则要判断：if操作符栈顶元素，压入OPTR栈。,栈的应用（表达式求值）,28,栈的应用（表达式求值）,29,StatusEvaluateExpression(OperandType/EvaluateExpression,此函数在哪里？,30,例4汉诺仪（Hanoi）塔传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界末日到来。,分析：设三根柱子分别为x，y,z,盘子在x柱上，要移到z柱上。1、当n=1时，盘子直接从x柱移到z柱上；2、当n1时,则设法将前n1个盘子借助z，从x移到y柱上，把盘子n从x移到z柱上；把n1个盘子从y移到z柱上。,n,n1,31,VoidHanoi(intn,charx,chary,charz)/将n个编号从上到下为1n的盘子从x柱，借助y柱移到z柱if(n=1)move(x,1,z);/将编号为1的盘子从x柱移到z柱else/将n-1个编号从上到下为1n-1的盘子从x柱，借助y柱移到z柱Hanoi(n-1,x,z,y);move(x,n,z);/将编号为n的盘子从x柱移到z柱/将n-1个编号从上到下为1n-1的盘子从y柱，借助x柱移到z柱Hanoi(n-1,y,x,z);/Hanoi,32,定义,3.2队列,与同线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。基本操作有入队或出队，建空队列，判队空或队满等操作。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）,33,队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾即an端，称为队尾；表头即a1端，称为队头。它是一种先进先出（）的线性表。,例如：队列Q=(a1,a2,a3,.,an-1,an),插入元素称为入队；删除元素称为出队。,队头,队尾,教材P59对队列有更详细定义：,队列的抽象数据类型定义见教材5960队列的存储结构为链队或顺序队（常用循环顺序队）,34,链队列示意图,讨论：空队列的特征？,怎样实现入队和出队操作？入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：front-next=p-next;,完整动作设计参见教材P61-62,队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,35,顺序队示意图,(队尾),(队首),队列会满吗？很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。,空队列的特征？约定：front=rear,队尾后地址,入队(尾部插入)：vrear=e;rear+;出队(头部删除)：x=vfront;front+;,讨论：,假溢出,有缺陷,怎样实现入队和出队操作？,3.2队列,36,问：什么叫“假溢出”？如何解决？,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,3.2队列,解决假溢出的途径采用循环队列,37,循环队列（臆造）,顺序队列,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，令队满特征为front=(rear+1)%N；,38,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,问2：在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,5,问1：左图中队列长度L=？,39,例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4,40,例2：数组n用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（）rf（）（nfr）%n（）nrf（）（nrf）%n,4种公式哪种合理？当rf时（A）合理；当rf时（C）合理；,分析：,综合2种情况，以（D）的表达最为合理,例3：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先，后。,移动队首指针,取出元素,41,循环队列的操作实现,1）初始化一空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，即front=rear=0（也可为任意单元，如2，或4）;,42,算法：,StatusInitQueue(SqQueue,新开单元的地址为0则表示内存不足,43,算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满if(q.rear+1)%QUEUE_MAXSIZE)=q.front)returnERROR;(2）插入动作q.baseq.rear=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;,2）入队操作,44,StatusEnQueue(SqQueue,2）入队操作（完整函数）,45,3）出队操作,算法说明：删除队头元素，返回其值e分析：（1）在删除前应当判断队列是否空；if(q.front=q.rear)returnERROR;（2）插入动作分析；因为队头指针front指向队头元素的位置，所以：e=q.baseq.front;q.front=(q.front+1)%QUEUE_MAXSIZE;,46,StatusDeQueue(SqQueue/DeQueue,算法：,47,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）；操作系统中多道作业的处理（一个CPU执行多个作业）；3.简化程序设