第三章栈和队列.ppt

经济与管理学院李春丽,数据结构,第三章栈和队列,栈,栈的应用举例,队列,课堂练习,3.1栈,逻辑结构：与线性表相同;存储结构:顺序存储和链式存储;运算:比线性表有更多的限制,则称为运算受限的线性表.,栈与队列是两种特殊的线性表:,3.1.1栈的概念和运算,1、栈的基本概念,空栈：不含任何数据元素的栈。,栈：限定仅在一端进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。数据元素之间的逻辑关系：一对一。,（a1,a2,an）,3.1.1栈的概念和运算,注：栈的运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。入栈：插入元素到栈顶（即表尾）的操作。出栈：从栈顶（即表尾）删除最后一个元素的操作。问：栈与一般线性表有什么不同？一般线性表（堆）栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)入栈操作演示出栈操作演示,3.1.1栈的概念和运算,a1,a2,a3,入栈,插入：入栈、进栈、压栈,入栈的操作示图：,3.1.1栈的概念和运算,a1,a2,a3,删除：出栈、弹栈,出栈的操作示图：,栈的操作特性：后进先出,出栈,3.1.1栈的概念和运算,思考题：一个栈的输入序列为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种可能性。,3.1.1栈的概念和运算,思考题：,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：）a，b，c，d）c，d，a，b）b，c，d，a）a，c，d，b,A、D可以（B、C不行）。,讨论：有无通用的判别原则？有。若输入序列i，j，k，则不存在输出序例k、i、j;,答：,3.1栈的类型定义,ADTStack数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。,基本操作：,ADTStack,3.1.1栈的概念和运算,2、栈的基本操作,1）InitStack(#defineSTACKINCREMENT10;typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;,3.1.2顺序栈,StatusInitStack(SqStack,StatusPush(SqStack,StatusPop(SqStack,链栈,S,data,next,栈顶,栈底,3.2栈的应用举例,调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题；其它应用：如括号匹配问题、表达式计算问题等。,答：,为什么要设计栈？它有什么独特用途？,3.2栈的应用举例,例1:文字编辑器规定:输入#:表示删除前面一个字符;输入:表示删除前面所有字符;输入*:表示输入结束.,eg：ab#cdef#g*,deg,出栈,置空栈,voidLineEdit()/利用字符栈S，从终端接收一行并传送至调用过程的数据区。InitStack(s);ch=getchar();while(ch!=BOF)/BOF为全文结束符while(ch!=BOF,3.2栈的应用举例,例2:栈与递归,递归：子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。,3.2栈的应用举例,求阶乘函数,递归算法intFACT(intn)if(n=1)return1;elsereturnn*FACT(n-1);,3.2栈的应用举例,求解阶乘n!的过程,计算fact(4),递归调用,回归求值,3.2栈的应用举例,经典问题汉诺塔问题,在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。,3.2栈的应用举例,汉诺塔问题的递归求解方法:如果n=1，则将这一个盘子直接从塔A移到塔C上。否则，执行以下三步：将塔A上的n-1个碟子借助塔C先移到塔B上；,3.2栈的应用举例,把塔A上剩下的一个碟子移到塔C上；将n-1个碟子从塔B借助于塔A移到塔C上。,3.2栈的应用举例,算法实现：voidHanoi(intn,charA,charB,charC)if(n=1)Move(A,C);elseHanoi(n-1,A,C,B);Move(A,C);Hanoi(n-1,B,A,C);,3.2栈的应用举例,Hanio(3,A,B,C),Hanio(2,A,C,B),Hanio(1,A,B,C),Move(A,C),Move(A,B),Hanio(1,C,A,B),Move(C,B),Move(A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move(B,C),Hanio(1,A,B,C),Move(A,C),Move(B,A),汉诺塔递归调用过程：,3.4队列,队列（Queue）:先进先出(FirstInFirstOut)(缩写为FIFO）的线性表。仅在队尾进行插入、队头进行删除的线性表。队头（front）:线性表的表头端，即可删除端。队尾（rear）:线性表的表尾端，即可插入端。,队头,对尾,.,a1,a2,a3,an-1,an,ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an端为队列尾,基本操作：,3.4.1队列的类型定义,ADTQueue,队列的基本操作：,InitQueue(否则返回FALSE。QueueLength(Q)初始条件:队列Q已经存在。操作结果:返回队列Q中的数据元素个数,即队列Q的长度。GetHead(Q,structQNode*next;QNode,*QueuePtr;,3.4.2链队列链式表示,typedefstruct/链队列类型QueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,StatusInitQueue(LinkQueue,StatusEnQueue(LinkQueue,StatusDeQueue(LinkQueue,3.4.3循环队列-队列的顺序表示与实现,采用顺序存储结构约定:1)初始空队列：front=rear=0;2)插入新的元素时,rear+;3)删除队头元素时,front+;,3.4.3循环队列-队列的顺序表示与实现,循环队列-解决数组越界但未占满空间的办法,当Q.rearQ.front时:Q.rearQ.front=队列中元素个数当Q.rearQ.front时:Q.rearQ.front+maxsize=队列中元素个数当Q.rear=Q.front时:队列是空或满,解决方案：,（1）设标志位以区别队列“空”还是“满”；intflag；0：非空1：空（2）少用一个元素空间，约定以“队列头指针在队尾指针的下一位置”作为队列“满”状态的标志。Q.front=Q.rear+1,循环队列的头尾指针,#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/动态分配存储空间intfront;/头指针，若队列不空，/指向队列头元素intrear;/尾指针，若队列不空，指向/队列尾元素的下一个位置SqQueue;,循环队列顺序表示和实现,StatusInitQueue(SqQueue,StatusEnQueue(SqQueue,StatusDeQueue(SqQueue,本章小结,掌握栈和队列的特点，并能在相应的应用问题中正确选用它们。熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。理解递归算法执行过程中栈的状态变化过程。,课堂练习,一选择题1.对于栈操作数据的原则是（）。【青岛大学2001五、2（2分）】A.先进先出B.后进先出C.后进后出D.不分顺序,【参考答案】B,课堂练习,2.在作进栈运算时,应先判别栈是否(),在作退栈运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。【上海海运学院1997二、1（5分）】【上海海运学院1999二、1（5分）】,:A.空B.满C.上溢D.下溢:A.n-1B.nC.n+1D.n/2:A.长度B.深度C.栈顶D.栈底:A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.,【参考答案】BABDC,3.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。【中山大学1999一、9(1分)】A.不确定B.n-i+1C.iD.n-i,课堂练习,【参考答案】B,4.若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（）。【武汉大学2000二、3（2分）】A.i-j-1B.i-jC.j-i+1D.不确定的,课堂练习,【参考答案】D,5.若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是()。【南京理工大学2001一、1（1.5分）】A.iB.n-iC.n-i+1D.不确定,课堂练习,【参考答案】D,课堂练习,6.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）【北方交通大学2001一、3（2分）】A.543612B.453126C.346521D.234156,【参考答案】C,课堂练习,7.设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，,【参考答案】D,公式C(2n,n)/(n+1)应该有14种情况ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA,课堂练习,8.元素A、B、C、D依次进栈，写出所有可能的出栈序列,9.栈和队列的共同点是（）。【燕山大学2001一、1（2分）】A.都是先进先出B.都是先进后出