三章节栈与队列.ppt

《三章节栈与队列.ppt》由会员分享，可在线阅读，更多相关《三章节栈与队列.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三章节栈与队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望学习要点：学习要点：o栈的基本概念、结构特征和操作要点。栈的基本概念、结构特征和操作要点。o栈在顺序存储和链式存储结构下各种操作的实现，栈满与栈栈在顺序存储和链式存储结构下各种操作的实现，栈满与栈空判定条件。空判定条件。o队列基本概念、结构特征和操作要点。队列基本概念、结构特征和操作要点。o队列在两种存储结构下各种操作如何实现，队满与队空判定队列在两种存储结构下各种操作如何实现，队满与队空判定条件。条件

2、。o循环队列基本概念，循环队列的队空与队满判定条件。循环队列基本概念，循环队列的队空与队满判定条件。o栈和队列的基本应用和应用要点。栈和队列的基本应用和应用要点。3.1栈栈3.1.1栈的基本概念栈的基本概念栈的例子栈的例子：操作系统中中断现场的保留等。：操作系统中中断现场的保留等。定义：定义：限定只能在限定只能在表的一端表的一端进行插入或删进行插入或删除操作的线性表。除操作的线性表。修改原则修改原则：后进先出后进先出（LIFO）练习：练习：o设进栈顺序为设进栈顺序为1、2、3、4，请说出以下的出栈顺，请说出以下的出栈顺序是否可能？序是否可能？A、1234B、4312C、2143D、3214E、

3、3421F、3412栈的抽象数据类型：栈的抽象数据类型：oADTStackiso数据对象：数据对象：D=ai|ai DataType,i=0,1,2,n-1,n0o数据关系：数据关系：R=|ai-1,ai D,i=1,2,n-1约定约定an-1为栈为栈顶，顶，a0为栈底。为栈底。o基本操作：基本操作：o（1）StackInitStack()初始化并返回一个空栈；初始化并返回一个空栈；o（2）ClearStack(StackS)清空栈清空栈S中的元素；中的元素；o（3）intIsEmpty(StackS)判断栈是否为空，返回栈空或非空标志；判断栈是否为空，返回栈空或非空标志；o（4）intIsF

4、ull(StackS)判断栈是否满，返回栈满或不满标志；判断栈是否满，返回栈满或不满标志；o（5）StackPush(StackS,DataTypex)若栈未满，将数据元素若栈未满，将数据元素x入栈；入栈；o（6）StackPop(StackS)若栈非空，删除栈顶元素；若栈非空，删除栈顶元素；o（7）DataTypeGetTop(StackS)若栈非空，返回栈若栈非空，返回栈S中的取栈顶元素；中的取栈顶元素；oADTStack3.1.2栈的顺序存储结构栈的顺序存储结构o数组定义栈：数组定义栈：stackmaxmax-110o规定：规定：top指向栈顶元素所在位置指向栈顶元素所在位置o初始：初始

5、：top=-1（空栈）（空栈）空栈：空栈：top=-1，出栈下溢，出栈下溢栈满：栈满：top=max-1，进栈上溢，进栈上溢3.1.2栈的顺序存储结构栈的顺序存储结构2(a)(a)空空栈栈 (b)(b)栈栈中有两个元素中有两个元素 (c)(c)栈满栈满图图3-2 3-2 顺顺序序栈栈各种情况各种情况3.1.2栈的顺序存储结构栈的顺序存储结构3用用C语言定义栈的顺序存储结构如下：语言定义栈的顺序存储结构如下：#defineMAXSIZE100/*MAXSIZE指的是栈的最大长度指的是栈的最大长度*/typedefstructDataTypeelemMAXSIZE;/*定义数组依次存放栈里的数据元

6、素定义数组依次存放栈里的数据元素*/inttop;/*指向栈顶元素的下标指向栈顶元素的下标*/Stack;基本操作：顺序栈初始化基本操作：顺序栈初始化算法要求返回一个空的栈，空栈中数据元素个数为算法要求返回一个空的栈，空栈中数据元素个数为0，top值为值为-1。00StackInitStack()0102StackS;03S.top=-1;/*空栈的空栈的top值为值为-1*/04return(S);05基本操作：进栈基本操作：进栈已知栈已知栈S及数据元素及数据元素x，需要将，需要将x放置进栈放置进栈S00StackPush(StackS,DataTypex)/*若栈未满，将数据元素若栈未满，

7、将数据元素x入栈入栈*/0102if(S.top=MAXSIZE-1)03printf(“栈已满，无法入栈！栈已满，无法入栈！”);04else0506S.top=S.top+1;07S.elemS.top=x;0809return(S);10基本操作：出栈基本操作：出栈00StackPop(StackS)/*若栈非空，删除栈顶元素若栈非空，删除栈顶元素*/0102if(S.top=-1)03printf(“栈是空的，无法出栈！栈是空的，无法出栈！”);04else05S.top=S.top-1;06return(S);07基本操作：取栈顶元素基本操作：取栈顶元素已知栈已知栈S，取出栈顶元素，

8、取出栈顶元素00DataTypeGetTop(StackS)/*若栈非空，取栈顶元素赋值给若栈非空，取栈顶元素赋值给x*/0102if(S.top=-1)03printf(“栈是空的，无法取栈顶！栈是空的，无法取栈顶！”);04else05x=S.elemS.top;06return(x);07多栈共享技术：双端栈多栈共享技术：双端栈原理：原理：利用栈只能在栈顶端进行操作的特性，将两个栈的栈底分别设在利用栈只能在栈顶端进行操作的特性，将两个栈的栈底分别设在数组的头和尾，两个栈的栈顶在数组中动态变化，栈数组的头和尾，两个栈的栈顶在数组中动态变化，栈1元素比较多时就占元素比较多时就占用比较多的存储

9、单元，元素少时就让出存储单元供栈用比较多的存储单元，元素少时就让出存储单元供栈2可用，提高了数组可用，提高了数组的利用率。的利用率。图图3-3 双端双端栈栈3.1.3栈的链式存储结构栈的链式存储结构规定：规定：top指向栈顶元素地址指向栈顶元素地址链栈中结点结构和单链表一样，指针域指向链栈中结点结构和单链表一样，指针域指向次顶元素次顶元素。datalink设指针域指向次顶结点设指针域指向次顶结点用用C语言可定义如下：语言可定义如下：00structnode0102DataTypedata;03structnode*next;04;05typedefstructnodeStackNode;06S

10、tackNode*top;3.1.4栈的链式存储结构栈的链式存储结构图图3-5 3-5 链栈链栈基本操作：链栈初始化基本操作：链栈初始化初始化链栈即建立一个空的链栈，只有初始化链栈即建立一个空的链栈，只有top结点，其指针域为空。结点，其指针域为空。00StackNode*InitStack()0102StackNode*top;03top=(StackNode*)malloc(sizeof(StackNode);04top-next=NULL;05return(top);06基本操作：进栈基本操作：进栈已知一个数据元素已知一个数据元素x以及链栈以及链栈top，要求完成，要求完成x进栈操作。进

11、栈操作。基本操作：进栈基本操作：进栈200StackNode*Push(StackNode*top,DataTypex)0102StackNode*p;03p=(StackNode*)malloc(sizeof(StackNode);/*申请结点申请结点p*/04p-data=x;/*x存储到新结点存储到新结点p中中*/05p-next=top-next;/*p指向栈顶结点指向栈顶结点*/06top-next=p;/*top结点指向结点指向p，p成为新的栈顶成为新的栈顶*/07return(top);08基本操作：出栈基本操作：出栈基本操作：出栈基本操作：出栈200StackNode*Pop(

12、StackNode*top)0102StackNode*p;03if(top-next=NULL)/*判断栈是否为空判断栈是否为空*/0405printf(“栈空，无法出栈！栈空，无法出栈！”);06return(top);0708p=top-next;/*p指向栈顶，待删除指向栈顶，待删除*/09top-next=p-next;/*top结点指针域跳过结点指针域跳过p，指向，指向p的后继的后继*/10free(p);/*释放释放p占用的空间占用的空间*/11return(top);123.1.4栈的应用栈的应用1.栈在递归程序中的应用栈在递归程序中的应用阶乘运算阶乘运算递归问题的解决可以大致

13、做这样的算法描述：递归问题的解决可以大致做这样的算法描述：if（递归结束条件）（递归结束条件）return(递归结束条件下的返回值）；递归结束条件下的返回值）；elsereturn（递归计算公式）；（递归计算公式）；3.1.4栈的应用栈的应用1.栈在递归程序中的应用栈在递归程序中的应用阶乘运算阶乘运算解释：解释：递归计算公式：递归计算公式：是大问题在变成次大问题中的表现出来的规律，是大问题在变成次大问题中的表现出来的规律，要表达清楚这个大问题与下一级的次大问题有什么联系。要表达清楚这个大问题与下一级的次大问题有什么联系。递归结束条件：递归结束条件：解决递归问题中的分解不能无终止地分解下去，解决

14、递归问题中的分解不能无终止地分解下去，需有一个结束的条件。这样才可以由结束递归再返回层层解套，需有一个结束的条件。这样才可以由结束递归再返回层层解套，最终解决整个问题。递归的结束条件也称为递归出口。最终解决整个问题。递归的结束条件也称为递归出口。3.1.4栈的应用栈的应用例子：例子：n的阶乘的计算的阶乘的计算n!=1(n=0,1)n*(n-1)!(n1)3.1.4栈的应用栈的应用例子：例子：n的阶乘的计算的阶乘的计算00intfact(intn)0102intfac;03if(n=0)04fac=1;05else06fac=fact(n-1)*n;07returnfac;083.1.4栈的应用

15、栈的应用22.栈在递归程序中的应用栈在递归程序中的应用Hanoi塔问题塔问题解释解释Hanoi游戏游戏:（1）设有三根杆子）设有三根杆子A,B,C。A杆上有杆上有n个盘子，从小到个盘子，从小到大相叠着，编号大相叠着，编号1n；（2）每次移动一块盘子到另外一个杆上）每次移动一块盘子到另外一个杆上,但要求每个杆但要求每个杆上的盘子只能是小的叠在大的上面；上的盘子只能是小的叠在大的上面；（3）把所有盘子从）把所有盘子从A杆全部移到杆全部移到C杆上，可利用杆上，可利用B杆作杆作为过渡。为过渡。3阶阶Hanoi问题求解过程：问题求解过程：3.1.4栈的应用栈的应用2n阶阶Hanoi递归算法递归算法：00

16、voidHannoi(intn,charA,charB,charC)0102if(n=1)03Move(1,A,C);/*将将1号盘从号盘从A杆移到杆移到C杆杆*/04else0506Hannoi(n-1,A,C,B);/*将将A杆上杆上n-1个盘借助个盘借助C杆移动到杆移动到B杆杆*/07Move(n,A,C);/*将将n号盘从号盘从A杆移到杆移到C杆杆*/08Hannoi(n-1,B,A,C);/*将将B杆上杆上n-1个盘借助个盘借助A杆移动到杆移动到C杆杆*/09103.1.4栈的应用栈的应用3n阶阶Hanoi非非递归算法递归算法见见3.1.4节算法节算法3-11。3.1.4栈的应用栈的

17、应用33.栈在括号匹配中的应用栈在括号匹配中的应用问题理解问题理解:假设一个算术表达式中包含圆括号、方括号和花括号假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法，判别表达式中括号是否三种类型的括号，编写一个算法，判别表达式中括号是否正确配对。正确配对。如如“fhabh(gfhggt)qgfr”是正确匹配的，是正确匹配的，“fdsfsd(gfdg”则缺少则缺少“)”。3.1.4栈的应用栈的应用33.栈在括号匹配中的应用栈在括号匹配中的应用程序见程序见3.1.4节算法节算法3-12。顺序扫描被判别的表达式，每当遇到顺序扫描被判别的表达式，每当遇到（、或或时，将时，将其压

18、入栈中（算法其压入栈中（算法3-12第第11-14行）；当遇到行）；当遇到）、或或时，先检查栈是否是空的，如果是空的，表示缺少对应的左边括号，时，先检查栈是否是空的，如果是空的，表示缺少对应的左边括号，接着检查当前栈顶元素是否是对应的接着检查当前栈顶元素是否是对应的（、或或，若是则退，若是则退栈，否则返回表示不匹配。如对栈，否则返回表示不匹配。如对）的处理（程序中第的处理（程序中第15-28）。）。当整个算术表达式检查完毕时，还要对栈的情况进行判断，如栈是当整个算术表达式检查完毕时，还要对栈的情况进行判断，如栈是空的说明所有左右括号相匹配，否则缺少栈内左括号相对应的右括空的说明所有左右括号相匹

19、配，否则缺少栈内左括号相对应的右括号（程序中第号（程序中第56-59行）。行）。程序设计要点程序设计要点:3.1.4栈的应用栈的应用44.栈在表达式求值中的应用栈在表达式求值中的应用（1 1）由计算规则得算符优先关系表）由计算规则得算符优先关系表 3+5*3 3+5+5 3+5*3 3+5+5 1 1：先来的算符：先来的算符 22：后来的算符：后来的算符=（-+）*-+124.栈在表达式求值中的应用栈在表达式求值中的应用2（2）原理原理两工作栈：一个算符栈，一个操作数栈两工作栈：一个算符栈，一个操作数栈a.读取到操作数，直接入操作数栈读取到操作数，直接入操作数栈b.读取到运算符，取运算符栈栈顶

20、元素与该算符比较优读取到运算符，取运算符栈栈顶元素与该算符比较优先级：先级：“”：运算符栈出一元素，操作数栈出两元素，运算符栈出一元素，操作数栈出两元素，运算后，结果放回操作数栈；运算后，结果放回操作数栈；“=”：运算符栈出一元素，与之相抵消。运算符栈出一元素，与之相抵消。4.栈在表达式求值中的应用栈在表达式求值中的应用3计算计算#3*（15-5）/2#栈的变化过程栈的变化过程4.栈在表达式求值中的应用栈在表达式求值中的应用2（2）原理原理算法结束标志：算法结束标志：运算符栈为空，操作数栈有一元运算符栈为空，操作数栈有一元素，即为结果。素，即为结果。表达式求值表达式求值算法算法见见3.1.4节

21、算法节算法3-13。上机（选做）：上机（选做）：o输入十进制数，转换成输入十进制数，转换成R进制数。进制数。o输入一包含输入一包含“(”和和“)”的字符串，检测括号是否匹配（其中的字符串，检测括号是否匹配（其中括号中能嵌套括号），并输出括号是否匹配的信息（匹配、缺括号中能嵌套括号），并输出括号是否匹配的信息（匹配、缺少左括号、缺少右括号）；少左括号、缺少右括号）；分析：分析：ogets(fun)owhile(funi!=0)oif(funi=()：入栈；：入栈；oif(funi=)：oif栈空：栈空：错，错，缺左边，缺左边，return；oelse出栈；出栈；oi=i+1;oo如栈空如栈空对！

22、对！o否则否则错，错，缺少右边缺少右边3.2队列队列3.2.1队列基本概念队列基本概念o队列的例子：排队等。队列的例子：排队等。定义：定义：限定只能在表的一端进行插入，在表的另一端限定只能在表的一端进行插入，在表的另一端进行删除的线性表。进行删除的线性表。修改原则：先进先出（修改原则：先进先出（FIFO）图图3-11 队队列示意列示意图图队列抽象数据类型：队列抽象数据类型：ADTQueueiQ基本操作：基本操作：数据对象：数据对象：D=ai|ai DataType,i=0,1,2,n-1,n0数据关系：数据关系：R=|ai-1,ai D,i=1,2,n-1约定约定an-1为队尾，为队尾，a0为

23、队头。为队头。（1）QueueInitQueue()初始化并返回一个空队列；初始化并返回一个空队列；（2）ClearQueue(QueueQ)清空队列清空队列Q中的元素；中的元素；（3）intIsEmpty(QueueQ)判断队列是否为空，返回队列空或非空标志；判断队列是否为空，返回队列空或非空标志；（4）intIsFull(QueueQ)判断队列是否满，返回队列满或不满标志；判断队列是否满，返回队列满或不满标志；（5）QueueInserQ(QueueQ,DataTypex)若队列未满，将数据元素若队列未满，将数据元素x入队列；入队列；（6）QueueDeleteQ(QueueQ)若队列非空

24、，删除队头元素；若队列非空，删除队头元素；（7）DataTypeGetHead(QueueQ)若队列非空，返回队列若队列非空，返回队列Q中的队头元素；中的队头元素；（8）DataTypeGetRear(QueueQ)若队列非空，返回队列若队列非空，返回队列Q中的队尾元素；中的队尾元素；ADTQueue3.2.2顺序队列与循环队列顺序队列与循环队列o数组定义队列：数组定义队列：queuemaxmax-110o规定：规定：front指向队头元素位置指向队头元素位置rear指向队尾元素的下一个空位指向队尾元素的下一个空位o初始：初始：front=rear=0o队空：队空：front=rearo队满：

25、队满：rear=max3.2.2顺序队列与循环队列顺序队列与循环队列2(a)(a)空空队队列列 (b)(b)队队列中有列中有3 3个元素个元素 (c)(c)队队列列3 3个元素出个元素出队队 (d)(d)队满队满图图3-12 3-12 顺顺序序队队列各种情况列各种情况3.2.2顺序队列与循环队列顺序队列与循环队列3o假溢出的问题：用循环队列来解决假溢出的问题：用循环队列来解决下一个下一个rear计算公式：计算公式：rear=（rear+1）modmax3.2.2顺序队列与循环队列顺序队列与循环队列4o循环队列队空队满标志冲突的问题：循环队列队空队满标志冲突的问题：以牺牲一个存储空间为代价，当判

26、断到以牺牲一个存储空间为代价，当判断到（下一个（下一个rear=front）时，即认为队满。时，即认为队满。实际上，实际上，max个空间只存放了（个空间只存放了（max-1）个元素）个元素o循环队列队空、队满标志：循环队列队空、队满标志：队满：队满：（rear+1）modmax=front队空：队空：front=rear冲突解决！冲突解决！3.2.2顺序队列与循环队列顺序队列与循环队列5练习：练习：o设循环队列容量为设循环队列容量为70（序号（序号069），现经过一系），现经过一系列的入队和出队后，问下列情况下循环队列中各有几列的入队和出队后，问下列情况下循环队列中各有几个元素？个元素？（1）

27、front=14，rear=21（2）front=23，rear=12基于基于C语言的顺序队列的类型定义：语言的顺序队列的类型定义：00#defineMAX10001typedefstruct0203DataTypeelemMAX;/*定义数组依次存放队列里的数据元素定义数组依次存放队列里的数据元素*/04intfront;/*指向队头元素的下标指向队头元素的下标*/05intrear;/*指向队尾元素的下一个空位指向队尾元素的下一个空位*/06Queue;基本操作：初始化队列基本操作：初始化队列00QueueInitQueue()0102QueueQ;03Q.front=Q.rear=0;/

28、*队列初始化时队列初始化时front=rear=0*/04return(Q);05基本操作：进队列基本操作：进队列00QueueInserQ(QueueQ,DataTypex)0102if(Q.rear+1)%MAX=Q.front)03printf(“队列已满，无法进队！队列已满，无法进队！”);04else0506Q.elemQ.rear=x;/*x进队列进队列*/07Q.rear=(Q.rear+1)%MAX;/*rear指向队尾下一个空位指向队尾下一个空位*/0809return(Q);10基本操作：出队列基本操作：出队列00QueueDeleteQ(QueueQ)/*若栈非空，删除栈

29、顶元素若栈非空，删除栈顶元素*/0102if(Q.rear=Q.front)03printf(“队列是空的，无法出队！队列是空的，无法出队！”);04else05Q.front=（Q.front+1）%MAX;06return(Q);07基本操作：访问队头元素基本操作：访问队头元素00DataTypeGetHead(QueueQ)/*若队列非空，取队头元素赋值给若队列非空，取队头元素赋值给x*/0102if(Q.rear=Q.front)03printf(“队列是空的，无法取队头！队列是空的，无法取队头！”);04else05x=Q.elemQ.front;06return(x);073.2.

30、3队列链式存储结构队列链式存储结构o1structnodeo2DataTypedata;/*链队列结点数据域类型及名称链队列结点数据域类型及名称*/o3structnode*next;/*指针域类型及名称，指向下一结点指针域类型及名称，指向下一结点*/o4;o5typedefstructnodeQueueNode;o6structnode2o7QueueNode*front;o8QueueNode*rear;o9;o10typedefstructnode2Queue;基本操作：链队列初始化基本操作：链队列初始化00QueueInitQueue()0102QueueQ;03Q.front=(Qu

31、eueNode*)malloc(sizeof(QueueNode);04Q.front-next=NULL;05Q.rear=Q.front06return(Q);07 frontrear基本操作：进队列基本操作：进队列00QueueInserQ(QueueQ,DataTypex)0102QueueNode*p;03p=(QueueNode*)malloc(sizeof(QueueNode);04p-data=x;/*x存储到新结点存储到新结点p中中*/05p-next=NULL;/*p的指针域置空的指针域置空*/06Q.rear-next=p;/*队尾指针域指向队尾指针域指向p，p成为新的队

32、尾成为新的队尾*/07Q.rear=p;/*队尾指针队尾指针rear指向指向p，保证，保证rear指向新的队尾指向新的队尾*/08return(Q);09基本操作：出队列基本操作：出队列00QueueDeleteQ(QueueQ)0102QueueNode*p;03if(Q.front=Q.rear)/*判断队列是否为空判断队列是否为空*/0408p=Q.front-next;/*p指向队头结点，待删除指向队头结点，待删除*/09Q.front-next=p-next;/*top结点指针域指向结点指针域指向p的后继的后继*/10if(p=Q.rear)/*如被删结点也是队尾结点如被删结点也是队

33、尾结点*/11Q.rear=Q.front;/*rear指向头结点指向头结点*/12free(p);/*释放释放p占用的空间占用的空间*/13return(Q);143.2.4队列应用队列应用1.共享打印机共享打印机2.CPU资源分配资源分配 3.2.4队列的应用队列的应用23.打印杨辉三角打印杨辉三角过程分过程分3步骤：步骤：（1）第）第6行中的第一个元素行中的第一个元素1进队。进队。（2）输出第）输出第5行中的前行中的前5个元素，并生成第个元素，并生成第6行中的行中的5个元素。循环个元素。循环5次，做：输出队头，次，做：输出队头，队头出队列赋值给队头出队列赋值给x，x与新队头相加进队列。与

34、新队头相加进队列。（3）输出第）输出第5行中的最后一个元素行中的最后一个元素1并换行，并换行，出队列。出队列。（4）第）第6行中的最后一个元素行中的最后一个元素1进队。进队。程序见程序见3.2.4节算法节算法3-21。基于循环队列的杨辉三角显示基于循环队列的杨辉三角显示:o设有一顺序栈设有一顺序栈S，元素，元素s1,s2,s3,s4,s5,s6依次入栈，依次入栈，如果出栈顺序为如果出栈顺序为s2,s3,s4,s6,s5,s1，栈的容量至少为，栈的容量至少为（）。）。A.2B.3C.5D.6练习练习:Bo设有一栈已有设有一栈已有a1,a2,a3三个元素三个元素,栈顶为栈顶为a3,a4正等待正等待

35、入栈入栈,则以下序列是不可能的出栈序列是则以下序列是不可能的出栈序列是()。A.a3,a1,a4,a2B.a3,a2,a4,a1C.a3,a4,a2,a1D.a4,a3,a2,a1Ao()在链队中在链队中,即使不设置尾指针也能进行入队操作即使不设置尾指针也能进行入队操作;o()在带头结点的链队中进行出队操作在带头结点的链队中进行出队操作,不会改变头结点地址不会改变头结点地址front的值的值;o()循环队列中元素个数为循环队列中元素个数为rear-frontTTFo以以S和和X分别代表入栈和出栈，对输入序列分别代表入栈和出栈，对输入序列a、b、c、d、e进行一系列栈操作进行一系列栈操作SSXSXSSXXX后得到的序列为：后得到的序列为：bcedao在一个链队中，如以在一个链队中，如以f和和r分别代表队头、队尾指针，则分别代表队头、队尾指针，则插入插入s结点的操作为：结点的操作为：r-next=s;r=s;本章小结本章小结本章基本内容本章基本内容