《【教学课件】第三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第三章栈和队列.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 栈和队列n n学习要点n n理解栈和队列的基本概念和各种存储结构；理解栈和队列的基本概念和各种存储结构；n n掌握栈和队列的各种运算方法掌握栈和队列的各种运算方法n n了解堆栈在递归运算中的应用了解堆栈在递归运算中的应用3.1 栈 栈的概念栈的概念 使用数组创建使用数组创建栈栈使用链表创建使用链表创建栈栈3.1.1 栈的概念栈的示意图出栈入栈栈顶ana2a1栈底n定义：定义：栈栈(Stack)是限制在一端进行插入是限制在一端进行插入和删除运算的线性表。通常称插和删除运算的线性表。通常称插入、删除的这一端为入、删除的这一端为栈顶栈顶(Top)，另一端为另一端为栈底栈底(Bottom)。当
2、表中当表中没有元素时称为没有元素时称为空栈空栈。（a1,a2,.,an ）插入删除栈的特点栈的特点后进先出后进先出(LIFO)(LIFO)栈的示意图出栈入栈TOPana2a1n栈顶：栈顶：对栈进行操作的一端。对栈进行操作的一端。n栈顶指针：栈顶指针：指示栈顶位置的指针。指示栈顶位置的指针。n栈的长度：栈的长度：栈中元素的个数。栈中元素的个数。n假设栈假设栈S=(a1，a2，a3，,an)，则，则a1称为称为栈底元素栈底元素，an为为栈顶栈顶元素元素。插入的过程称为入栈，删。插入的过程称为入栈，删除的过程称为出栈。栈中元素的除的过程称为出栈。栈中元素的出栈入栈是按照后进先出的原则出栈入栈是按照后
3、进先出的原则进行的。因此，栈称为后进先出进行的。因此，栈称为后进先出表（表（LIFO）。）。r rs sr rt ts sr rs sr rr r(a)调用调用a函数函数,r进栈进栈(c)调用调用c函数函数,t进栈进栈(e)返回返回a函数函数,s退栈退栈(b)调用调用b函数函数,s进栈进栈(d)返回返回b函数函数,t退栈退栈(f)返回主程序返回主程序,r退栈退栈 n栈在函数嵌套调用中的应用：栈在函数嵌套调用中的应用：n n栈的基本操作栈的基本操作InitStackInitStack(s)s)构造一个空栈构造一个空栈S SClearStack(s)ClearStack(s)将栈将栈S S清为空栈
4、。清为空栈。EmptyStack(s)EmptyStack(s)若栈若栈S S为空栈，返回为空栈，返回TRUETRUE，否则，否则FALSEFALSELenStack(s)LenStack(s)返回栈返回栈S S中元素的个数，即栈的长度中元素的个数，即栈的长度GetTop(s)GetTop(s)取出取出S S的栈顶元素的值的栈顶元素的值Push(s,x)Push(s,x)插入元素插入元素x x为新的栈顶元素为新的栈顶元素Pop(s,x)Pop(s,x)删除删除S S的栈顶元素，并返回其值的栈顶元素，并返回其值如何存储栈?进栈、出栈等操作如何实现？3.1.2 栈的顺序存储结构 n顺序栈顺序栈：是
5、利用一块地址连续的存储单元来存放栈中的元是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指示器素，同时要利用一个指示器top top 来指示栈顶元素的位置。来指示栈顶元素的位置。typedef structElemtype skMaxsize；int top;seqstack;seqstack *s;s-sks-top/当前栈顶元素栈的几种状态示意图栈的几种状态示意图 top1234空栈 有5个元素的栈 栈顶元素出栈 元素进栈 toptoptop12345123423栈顶指针top,指向实际栈顶位置，初值为-1top=-1,栈空，此时出栈，则下溢（underflow)top=M-1
6、,栈满，此时入栈，则上溢（overflow)当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？顺序栈的图示topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 11)进栈操作进栈操作 进栈函数分为两个步骤：进栈函数分为两个步骤：n 将栈顶的指针加将栈顶的指针加1。n 将要存放的数据存放在指针所指向的数组中。将要存放的数据存放在指针所指向的数组中。x 进栈前 x 进栈后topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1x1)进
7、栈操作进栈操作 int Push(seqstack*s,Elemtype x)if(s-top=Maxsize-1)printf(out of space!n);return(0);s-top+;s-sks-top=x;return(1);2）出栈操作）出栈操作出栈操作也分为两个步骤：出栈操作也分为两个步骤：n 取出目前栈指针所指数组元素的内容。取出目前栈指针所指数组元素的内容。n 将栈指针的内容减将栈指针的内容减1，即指向下一个栈元素。，即指向下一个栈元素。出栈操作前出栈操作后topMAX-1n-1n-210a an na an-1n-1a a2 2a a1 1topMAX-1n-1n-21
8、0a an na an-1n-1a a2 2a a1 12）出栈操作）出栈操作int Pop(seqstack*s,Elemtype*e)if(s-top=-1)printf(no element!n);return(0);*e=s-sks-top;s-top-;return(1);3）其它几种操作）其它几种操作seqstack*InitStack()/创建空栈创建空栈 seqstack*s;s=(seqstack*)malloc(sizeof(seqstack);if(!s)printf(“未完成空未完成空间间分配分配!n);return(null);s-top=-1;return(s);i
9、nt EmptyStack(seqstack*s)/栈的判空操作栈的判空操作 if（s-top=-1）s-top=Maxsize-1return(1);elsereturn(0);Elemtype GetTop(seqstack*s)/取栈顶元素取栈顶元素 if(EmptyStack(s)return(0);elsereturn(s-sks-top);注意：n n对对对对于于于于顺顺顺顺序序序序栈栈栈栈，入入入入栈栈栈栈时时时时，首首首首先先先先判判判判栈栈栈栈是是是是否否否否满满满满了了了了，栈栈栈栈满满满满的的的的条条条条件件件件为为为为：s-top=MAXSIZE-1s-top=MAXS
10、IZE-1，栈栈栈栈满满满满时时时时，不不不不能能能能入入入入栈栈栈栈；否则出现空间溢出。否则出现空间溢出。否则出现空间溢出。否则出现空间溢出。n n出出出出栈栈栈栈和和和和读读读读栈栈栈栈顶顶顶顶元元元元素素素素操操操操作作作作，先先先先判判判判栈栈栈栈是是是是否否否否为为为为空空空空，为为为为空空空空时时时时不能操作。不能操作。不能操作。不能操作。n n合合合合理理理理初初初初始始始始化化化化栈栈栈栈的的的的方方方方法法法法：先先先先为为为为栈栈栈栈分分分分配配配配一一一一个个个个基基基基本本本本容容容容量量量量，然后在应用过程中，当栈的空间不够时再逐步扩大。然后在应用过程中，当栈的空间不
11、够时再逐步扩大。然后在应用过程中，当栈的空间不够时再逐步扩大。然后在应用过程中，当栈的空间不够时再逐步扩大。栈的链式存储结构，也称链栈，如图所示：栈的链式存储结构，也称链栈，如图所示：data nextS栈顶栈底an-1ana13.1.2 栈的链式存储结构 typedef struct nodeElemtype data;struct node*next;stacknode,*LinkStack;链栈的存储结构链栈的存储结构链栈的存储结构链栈的存储结构:top1)进栈算法进栈算法int PushLinkStack(LinkStack S,Elemtype x)LinkStack p;p=(Li
12、nkStack)malloc(sizeof(StackNode);if(!p)printf(分配不成功分配不成功n);return(0);p-data=x;p-next=S-next;S-next=p;return(p);Sana1Px2)出栈算法出栈算法int PopLinkStack(LinkStack S,Elemtype*e)LinkStack p;if(S-next=null)printf(Not Existn);return(0);p=S-next;S-next=S-next-next;e=p-data;free(p);return(1);San-1ana1p1m栈1底栈1顶栈2底
13、栈2顶3.1.3 共享栈常采用将两个栈底设在可用空间的两端。仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对每个栈可用的最大空间就可能大于整个可用空间的一半m/2。有时，一个程序设计中，需要使用多个同一类型的栈，这时候可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，实现多个栈存储空间的动态分配。小结小结1 栈是限定仅能在栈是限定仅能在栈顶栈顶一端进行插入、删除操一端进行插入、删除操 作的线性表；作的线性表；2 栈的元素具有栈的元素具有后进先出后进先出
14、的特点；的特点；3 栈顶元素的位置由一个称为栈顶指针的变量栈顶元素的位置由一个称为栈顶指针的变量 指示，进栈、出栈操作要修改栈顶指针；指示，进栈、出栈操作要修改栈顶指针；3.2 3.2 栈的应用举例栈的应用举例r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程3结果：结果：2 5 0 4 2 5 0 4例1 数制转换n n十进制十进制十进制十进制N N和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基和其它进制数的转换是计算机实现计算的基本问题本问题本问题本问题,其中一个简单算法基于下列原理其中一个简单算
15、法基于下列原理其中一个简单算法基于下列原理其中一个简单算法基于下列原理:n nN=(N div N=(N div d d)1010 d d+N mod+N mod d dn n例如例如例如例如:(1348):(1348)1010=2=2 8 83 3+5+5 8 82 2+0+0 8+4=(2504)8+4=(2504)8 8 N N N div 8N div 8 N mod 8 N mod 81348 1348 168 168 4 4 168168 21 210 02121 2 25 52 02 02 2计算时从低位到高位顺序计算时从低位到高位顺序产生八进制数的各个数位产生八进制数的各个数位
16、显示时按从高位到显示时按从高位到低位的顺序输出低位的顺序输出void Transform()S=InitStack();scanf(%d,&n);while(n)Push(S,n%8);n=n/8;while(!EmptyStack(S)Pop(S,p);printf(%d,*p);利用栈利用栈“先进后出先进后出”的性质，的性质，把先产生的数位压入栈中，把先产生的数位压入栈中，然后再从栈顶依次弹出即可然后再从栈顶依次弹出即可3.3 3.3 栈与递归栈与递归什么是递归什么是递归什么是递归什么是递归一一一一个个个个对对对对象象象象（事事事事物物物物）的的的的组组组组成成成成包包包包含含含含了了了了
17、自自自自身身身身或或或或者者者者说说说说对对对对于于于于一一一一个个个个对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为对象的描述又用到了该对象本身的现象称为递归递归递归递归 。递递递递归归归归是是是是程程程程序序序序设设设设计计计计中中中中一一一一个个个个很很很很有有有有用用用用的的的的工工工工具具具具，许许许许多多多多数数数数学学学学函函函函数数数数的定义和程序设计等许多领域中都用到了递归。的定义和程序设计等许多领域中都用到了递归。的定义和程序设计等许多领域中都用到了递归。的定义和程序设计等许多领域中都用到了递归。A()A(
18、);A 直接调用自己直接调用自己B间接调用自己间接调用自己B()C()C();B();递归算法的编写递归算法的编写递归算法的编写递归算法的编写1 1）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）将问题用递归的方式描述（定义）2 2）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法）根据问题的递归描述（定义）编写递归算法问题的递归描述（定义）问题的递归描述（定义）问题的递归描述（定义）问题的递归描述（定义）递归定义包括两项递归定义包括两项递归定义包括两项递归定义包括两项 基本项（终
19、止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解；基本项（终止项）：描述递归终止时问题的求解；递递递递归归归归项项项项：将将将将问问问问题题题题分分分分解解解解为为为为与与与与原原原原问问问问题题题题性性性性质质质质相相相相同同同同，但但但但规规规规模模模模较较较较小小小小的的的的问题；问题；问题；问题；例例 阶乘函数阶乘函数n!=1*2*3*4*(n-1)*n n!=1*2*3*4*(n-1)*n n!n!递归定义递归定义递归定义递归定义n!=1 n!=1 当当当当 n=1 n=1 时时时时n!=n(n-1)!n!=n(
20、n-1)!当当当当n 1 n 1 时时时时用用(n-1)!(n-1)!定义定义n!n!计算计算计算计算5 5 5 5的阶乘（的阶乘（的阶乘（的阶乘（5 5 5 5！=5X4X3X2X1=5X4X3X2X1=5X4X3X2X1=5X4X3X2X1）int f(int n)int f(int n)int f(int n)int f(int n)if(n=1)return(1);if(n=1)return(1);if(n=1)return(1);if(n=1)return(1);else return(n*f(n-1);else return(n*f(n-1);else return(n*f(n-1
21、);else return(n*f(n-1);f(1)f(2)f(3)f(4)f(5)top1 f(1)=1 2*f(1)f(2)=2*f(1)3*f(2)f(3)=3*f(2)4*f(3)f(4)=4*f(3)5*f(4)f(5)=5*f(4)例1 阶乘函数void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);运行结果：1，2，2，3，3，3，例2 递归的执行情况分析 递归调用执行情况如下：递归调用执行情况如下：主程序主程序(1)print(w)w=3;3print(2);
22、（1）w=3 top(2)输出：输出：3,3,3w2print(1);（2）w=2 （1）w=3 top(3)输出：输出：2,2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)输出：输出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3)输出：输出：2,2(2)2(1)3top(4)输出：输出：1(3)1(2)2(1)3top(2)输出：输出：3,3,3 (1)3top返回返回(3)1(2)2(1)3top(4)0结束结束(1)print(w-1);for(i=1;ifont=0;Q-rear=0;return OK;2）入队操作）入队操作
23、 功能：功能：将元素将元素 x 插入队尾插入队尾 元素元素 x x 入队前入队前元素元素 x x 入队后入队后frontrearJ1J2J34 03 152frontrearJ1J2J3 x4 03 152Q-rear=(Q-rear+1)%Maxsize;Q-elemQ-rear=e;入队算法：入队算法：int EnQueue(SqQueue*Q,ElemType e)if(Q-rear+1)%Maxsize=Q-front)return ERROR;Q-rear=(Q-rear+1)%Maxsize;Q-elemQ-rear=e;return OK;2）出队操作）出队操作 功能：功能：删除
24、队头元素删除队头元素出队操作前出队操作前出队操作后出队操作后frontrearJ1J2J34 03 152frontJ1J2J34 03 152rearQ-front=(Q-front+1)%Maxsize;*e=Q-elemQ-front;int DeQueue(SqQueue*Q,ElemType*e)if(Q-front=Q-rear)return ERROR;Q-front=(Q-front+1)%Maxsize;*e=Q-elemQ-front;return OK;出队算法：出队算法：打印队列算法打印队列算法：（数组打印）：（数组打印）void print1(SqQueue*Q)fo
25、r(i=0;ielemi);printf(n);printf(“Q-front=,Q-front);printf(“Q-rear=,Q-rear);打印队列算法打印队列算法：（循环队列打印）：（循环队列打印）void print2(SqQueue*Q)i=(Q-front+1)%Maxsize;while(i!=Q-rear)printf(%d,Q-elemi);i=i+1;i=i%maxsize;printf(“Q-rear=,Q-rear);空链队列空链队列链队列图示链队列图示n n链队列Q.frontQ.reara1 1a2 2Q.frontQ.rear3.4.3 链队列-队列的链式表示
26、与实现n n链队列存储结构的C语言描述:typedef struct QsNodeelemtype data;struct QsNode*next;Qsnode;typedef struct Qsnode*front;Qsnode*rear;LinkQueue;1）队列初始化运算）队列初始化运算int InitQueue(LinkQueue*Q)Q-front=(Qsnode*)malloc(sizeof(Qsnode);if(!Q-front)return 0;Q-rear=Q-front;Q-front-next=NULL;return 1;Q.frontQ.rear2）队列入队运算）队列
27、入队运算将结点加入到队列将结点加入到队列将结点加入到队列将结点加入到队列QQ的尾端的尾端的尾端的尾端int InQuene(LinkQueue*Q,elemtype e)Qsnode*p;p=(Qsnode*p)malloc(sizeof(Qsnode);if(p=NULL)return 0;p-data=e;Q-rear-next=p;Q-rear=p;Q-rear-next=NULL;return 1;pea1 1Q.frontQ.rear3）队列出队运算）队列出队运算将队头元素删除将队头元素删除将队头元素删除将队头元素删除int DeQuene(LinkQueue *Q)Qsnode *
28、P;if(Q-front=Q-rear)return 0;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);return 1;a1 1a2 2Q.frontQ.rearp当只有一个元素时，当只有一个元素时，要修改尾指针要修改尾指针void print(LinkQueue*q)LinkQueue*p;p=q-front-next;while(p!=NULL)printf(%4d,p-data);p=p-next;4）队列打印运算）队列打印运算1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源
29、竞争问题；3）离散事件的模拟-模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程；在操作系统课程中会讲到n n队列的应用返回目录返回目录 小结小结1 队列是限定仅能在表尾一端进行插入，表队列是限定仅能在表尾一端进行插入，表 头一端删除操作的线性表；头一端删除操作的线性表；2 队列中的元素具有先进先出的特点；队列中的元素具有先进先出的特点；3 队头、队尾元素的位置分别由称为队头指队头、队尾元素的位置分别由称为队头指 针和队尾指针的变量指示；针和队尾指针的变量指示；4 入队操作要修改队尾指针，出队操作要修入队操作要修改队尾指针，出队操作要修 改队头指针；改队头指针；习题习题1
30、1、设将整数、设将整数1 1、2 2、3 3、4 4依次进栈，但只要出栈时栈非空，依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问则可将出栈操作按任何次序夹入其中，请回答下有问题：题：（1 1）若入栈次序为）若入栈次序为push(1)push(1)，pop()pop()，push(2)push(2)，push(3)push(3)，pop()pop()，pop()pop()，push(4)push(4)，pop()pop()，则出栈的数字，则出栈的数字序列为什么？序列为什么？（2 2）能否得到出栈序列）能否得到出栈序列423423和和432432？并说明为什么不能得？
31、并说明为什么不能得到或如何得到。到或如何得到。（3 3）请分析）请分析1 1、2 2、3 3、4 4的的2424种排列中，哪些序列可以通种排列中，哪些序列可以通过相应的入出栈得到。过相应的入出栈得到。3 3、循环队列的优点是什么？如何判断它的空和满？、循环队列的优点是什么？如何判断它的空和满？4 4、设长度为、设长度为n n的链队列用单循环链表表示，若只设头指的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？针，则怎样进行入队和出队操作；若只设尾指针呢？7 7、用第二种方法，即少用一个元素空间的方法来区别循、用第二种方法，即少用一个元素空间的方法来区别循环队列的
32、队空和队满，试设计置空队、判队空、判队环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。满、出队、入队及取队头元素等六个基本操作。9 9、指出下列程序段的功能是什么？、指出下列程序段的功能是什么？(1)void demo1(seqstack*s)(1)void demo1(seqstack*s)int I;arr64;n=0;int I;arr64;n=0;while(!stackempty(s)arrn+=pos(s);while(!stackempty(s)arrn+=pos(s);for(I=0;n;I+)push(s,arrI);for(I=0;n
33、;I+)push(s,arrI);(2)void demo2(seqstack*s,int m)(2)void demo2(seqstack*s,int m)seqstack t;int i;seqstack t;int i;initstack(t);initstack(t);while(!Stackempty(s)while(!Stackempty(s)if(I=pop(s)!=m)push(t,I);if(I=pop(s)!=m)push(t,I);While(!Stackempty(t)While(!Stackempty(t)i=pop(t);i=pop(t);push(s,I);push(s,I);