第3章 栈和队列

第3章栈和队列本章讲解栈和队列。要求理解栈和队列概念；掌握栈和队列的存储结构；掌握栈和队列的基本操作；灵活应用栈和队列。重庆的麻辣烫，成都的串串香。串串香吃起美味，背后的付出却艰辛，要把菜品一个一个串到一根竹签上，吃货才能一个一个吃出来。一把一把接着下锅，先下锅的先吃到。串起来是进栈，吃出去是出栈；下锅是进队列，出锅是出队列。提纲3.1栈基本概念3.2顺序栈3.3链栈3.4栈应用3.5队列基本概念3.6顺序队列3.7链队列3.8循环队列和优先队列3.9队列应用3.10栈和队列学习总结3.1栈基本概念栈是特殊的线性表，它只允许在线性表的一端操作。如图3.1所示，装乒乓球、网球、羽毛球的盒子皆属于栈类型。能够操作的这一端叫栈顶，不能操作的另一端叫栈底。显然，栈有“先进后出”或“后进先出”的特点。3.1栈基本概念栈的抽象数据接口IStack3.2顺序栈以顺序存储结构进行存储的栈称为顺序栈。3.2.1顺序栈存储结构顺序栈存储结构采用顺序存储方式，同顺序表存储结构，故顺序栈也可以用一维数组存储如图3.2所示，栈顶设置1个指针top指向栈顶元素（有的参考书将top指向栈顶元素的下1个位置，不影响理解）。3.2.1顺序栈存储结构举例：1个经验丰富的探险队队长带领若干队员进入1个狭长的溶洞，要求后面队员手拉手紧跟着，不能单独走以免走散。队长最先进洞，一路做返回记号，出洞却最后出来。在这个例子中，溶洞看作栈，队长和队员看作元素，这是个顺序栈。3.2.2顺序栈基本操作顺序栈类SqStack3.2.2顺序栈基本操作长度为5的顺序栈的基本操作如图3.3所示。3.2.2顺序栈基本操作1.栈判空和栈判满顺序栈栈判空和栈判满操作就是判断栈是否为空和是否已满。出栈时要判断栈是否为空，入栈时要判断栈是否为满，否则操作无效，增加开销。那么又如何实现的呢？我们来看看算法3.1。3.2.2顺序栈基本操作【算法3.1】判断顺序栈是否为空和是否已满。思路:由图3.3的（1）和（3）易知，根据top的值可以判断栈空和栈满。代码见算法3.13.2.2顺序栈基本操作2.入栈顺序栈入栈操作是指向栈中添加元素，在栈没有满的情况下。那么又如何实现的呢？我们来看看算法3.2。3.2.2顺序栈基本操作【算法3.2】顺序栈入栈。思路:由图3.3的（2）易知，在栈未满的情况下先将top加1，再将入栈元素赋值给top处元素。代码见算法3.23.2.2顺序栈基本操作3.出栈顺序栈出栈操作是指栈顶元素出栈，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.3。3.2.2顺序栈基本操作【算法3.3】顺序栈出栈。思路:由图3.3的（4）易知，先将出栈元素赋值给返回变量，再top减1。代码见算法3.33.2.2顺序栈基本操作4.取栈顶元素顺序栈取栈顶元素操作是指访问栈顶元素但栈顶元素不出栈，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.4。3.2.2顺序栈基本操作【算法3.4】顺序栈取栈顶元素。思路:

由图3.3的易知，取栈顶元素只需访问top指针指向的元素，将其输出。代码见算法3.43.3链栈以链式存储结构进行存储的栈称为链栈。3.3.1链栈存储结构链栈存储结构采用链式存储方式，同链表存储结构。如图3.4所示，用带头节点的单链表表示链栈，链栈的栈顶指针top指向单链表的首节点，单链表的尾节点为栈底节点。3.3.2链栈基本操作链栈节点类LinkNode描述链栈类LinkStack描述3.3.2链栈基本操作1.栈判空链栈栈判空同顺序栈栈判空，而链栈同链表一样不存在溢出，除非内存耗尽。因此链栈出栈时要判断栈是否为空而入栈时不需要判断是否为满。3.3.2链栈基本操作【算法3.5】判断链栈是否为空。思路:由图3.4易知，链栈为空同链表为空，此时只有头节点，top指针也指向头节点。代码见算法3.53.3.2链栈基本操作2.入栈链栈入栈操作类似单链表插入节点操作，但只能在头节点之后即栈顶处插入。3.3.2链栈基本操作【算法3.6】链栈入栈。思路:由图3.4易知，插入的节点插入到头节点之后；top指针指向插入节点。代码见算法3.63.3.2链栈基本操作3.出栈链栈出栈操作类似单链表删除节点操作，在栈没有空的情况下，但只能删除首节点即栈顶节点。3.3.2链栈基本操作【算法3.7】链栈出栈。思路:由图3.4易知，若链栈非空则删除首节点；若删除后链栈为空则将top指针指向头节点，否则将其指向下一个节点；返回删除节点的data值。若链栈为空则返回空。代码见算法3.73.3.2链栈基本操作4.取栈顶元素链栈取栈顶元素操作同顺序栈取栈顶元素操作，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.8。3.3.2链栈基本操作【算法3.8】链栈取栈顶元素。思路:若链栈不为空则返top指针指向的节点的data值，否则返回空。代码见算法3.83.4栈应用

3.4栈应用【进一步思考】若1个十进制数有小数，小数部分转换为二进制还需用到栈吗？答：不需要，因为小数部分产生的二进制数与产生顺序相同，产生1个输出1个即可。3.4栈应用【例3.2】利用栈进行括号匹配检查，对2个测试用例"{{}}()(hello){({world}{})}"和"{{}}()(hello){({world}(})}"进行测试，并分析算法的时空复杂度。思路：（1）从头遍历字符串，每个字符处理如下；（2）若遇左括号将其入栈；（3）若遇右括号：栈不为空时将其与栈顶元素比较：匹配则出栈，不匹配则返回false，栈为空时返回false；（4）字符指针移到下1位，重复（2）、（3），直到遍历完字符串；（5）若栈为空则返回true，否则返回false。代码见应用3.23.4栈应用【进一步思考】用递归算法可否实现括号匹配检查，为什么？答：可以，因为该问题可以把大规模问题分解为若干个相似小规模问题。3.4栈应用

3.4栈应用【进一步思考】汉诺塔问题可以用递归算法实现吗？答：可以，见后面递归章节内容。3.5队列基本概念队列也是特殊的线性表，它限制在一端插入，另一端删除。如图3.6所示，现实中的队列例子很多如排队购物、打饭、上公交、做核酸等皆属于队列类型。插入的那端叫队尾，删除的那端叫队头。显然，队列有“先进先出”或“后进后出”的特点。3.5队列基本概念队列的抽象数据接口IQueue描述3.6顺序队列以顺序存储结构进行存储的队列称为顺序队列。3.6.1顺序队列存储结构顺序队列存储结构采用顺序存储方式，同顺序表存储结构，故顺序队列也可以用一维数组存储。如图3.7所示，队头设置1个指针front指向队首元素，队尾设置1个指针rear指向队尾元素的下1个元素（有的参考书将front和rear指向向前的1个位置，不影响理解）。3.6.1顺序队列存储结构举例：2个老师带若干个小朋友出去旅游，无论走到哪里，为了保证安全，小朋友们排成队列，2个老师一前一后监管。在这个例子中，老师和小朋友组成的队列类似顺序队列，2个老师分别看作队头指针和队尾指针。3.6.2顺序队列基本操作顺序队列类SqQueue的描述3.6.2顺序队列基本操作长度为5的顺序队列的基本操作如图3.8所示。3.6.2顺序队列基本操作1.队列判空和队列判满顺序队列判空和判满操作就是判断队列是否为空和是否已满。出队时要判断队列是否为空，入队时要判断队列是否为满，否则操作无效，增加开销。3.6.2顺序队列基本操作【算法3.9】判断顺序队列是否为空和是否已满。思路:由图3.8的（1）和（4）易知，根据front和rear关系值可以判断队列空和队列满。代码见算法3.93.6.2顺序队列基本操作2.入队顺序队列入队操作是指向队列中插入元素，在队列没有满的情况下。3.6.2顺序队列基本操作【算法3.10】顺序队列入队。思路:由图3.8的（2）、（3）、（4）易知，在队列未满情况下入队时front指针不动，先赋值到rear处，再将rear指针向后移动1位。代码见算法3.103.6.2顺序队列基本操作3.出队顺序队列出队操作是指队头元素出队列，在队列没有空的情况下。3.6.2顺序队列基本操作【算法3.11】顺序队列出队。思路:由图3.8的（5）易知，在队列不空的情况下出队时front指针处元素保存，front指针向后移动1位，返回保存元素即出队元素。代码见算法3.113.6.2顺序队列基本操作4.取队头元素和取队尾元素顺序队列取队头元素操作是指访问队列的首元素，取队尾元素操作是指访问队列的尾元素。3.6.2顺序队列基本操作【算法3.12】顺序队列取队头元素和取队尾元素。思路:由图3.8易知，取队头元素可以访问front指针指向的元素；取队尾元素可以访问rear-1处的元素。代码见算法3.123.7链队列以链式存储结构进行存储的队列称为链队列。3.7.1链队列存储结构链队列存储结构采用链式存储方式，同链表存储结构。如图3.9所示，front指针指向队头节点，rear指针指向队尾节点。3.7.2链队列基本操作链队列类LinkQueue的描述3.7.2链队列基本操作长度为3的链队列的基本操作如图3.10所示。3.7.2链队列基本操作队列判空链队列判空操作就是判断队列是否为空。出队时要判断链队列是否为空，否则操作无效，增加开销。3.7.2链队列基本操作【算法3.13】判断链队列是否为空。思路:由图3.10的（1）易知，链队列为空时front和rear指针都指向头节点。代码见算法3.133.7.2链队列基本操作2.入队链队列入队操作是指在队列中插入节点。3.7.2链队列基本操作【算法3.14】链队列入队。思路:由图3.10的（2）、（3）易知，链队列入队时，若队列非空则尾插法1个节点，再将rear指向尾节点；若队列为空则头节点后插入，再将front和rear都指向插入之后的首节点。代码见算法3.143.7.2链队列基本操作3.出队链队列出队操作是指从队列中删除节点。3.7.2链队列基本操作【算法3.15】链队列出队。思路:由图3.10的（4）易知，链队列出队时，若队列为空则返回null；若队列非空：（1）只有1个节点情形：head的next置为null；front和rear都指向head。（2）不止1个节点情形：删除首节点；front指针指向下1个节点。代码见算法3.153.7.2链队列基本操作4.取队头元素和取队尾元素链队列取队头元素操作是指访问队列的首节点，取队尾元素操作是指访问队列的尾节点。3.7.2链队列基本操作【算法3.16】链队列取队头元素和取队尾元素。思路:由图3.10易知，若队列非空，取队头元素可以访问front指针指向的节点；取队尾元素可以访问rear指针指向的节点。若队列为空则返回空。代码见算法3.163.8循环队列和优先队列循环队列和优先队列都是特殊的队列，它们在应用中能够解决特殊问题。3.8.1循环队列

3.8.1循环队列2.解决方案将顺序队列的首尾相连构成1个环，进行队列操作时front和rear指针在这个环上移动，这样的队列称为循环队列或环形队列。循环队列可以把空余的空间利用起来，这样就解决了顺序队列的假溢出问题。如图3.11所示。3.8.1循环队列

3.8.1循环队列3.类描述和基本操作循环队列类CircleSqQueue和基本操作描述3.8.2优先队列问题的提出队列“先进先出”的特点决定了不能适应一些场景。举例：到医院看病，依次排队看病，但此时有病危病人送来，医生就得优先看他，但对于绝大多数人来讲还是先来先服务的队列模式。再举例：按照高考成绩从高到低录取排成队列，显然每1个成绩在队列中的位置也就确定了，无论成绩有没有增删。在这些例子中，都允许有插队现象，不然用前面介绍的队列模式不能满足实际需要。3.8.2优先队列2.解决方案将队列中的每个元素设置优先级，队头元素优先级最高，队尾元素优先级最低，即优先级高的先出队，这样的队列称为优先队列。利用优先队列让插队现象变得合理合情。优先队列的存储结构可以是顺序存储结构，也可以是链式存储结构。3.8.2优先队列3.类描述和基本操作优先队列节点类PriorityNode描述采用链式存储结构的优先队列类PriorityQueue和基本操作描述3.8.2优先队列从上面的节点类和操作描述可以看出，优先队列与普通队列相似，主要不同的是：（1）优先队列节点多了1个优先级属性；（2）进队操作时，首先要根据进队元素的优先级找到其插入位

置，再将其插入队列中。3.9队列应用【例3.4】打印杨辉三角形。输入：n，代表行数；输出：n行杨辉三角形。思路：（1）初始化1个空链队列，并将2个1入队列；（2）外层循环控制n行；（3）内层循环计算并打印列数字；（4）内外层循环之间入队1个0进行重置计算。代码见应用3.43.9队列应用【进一步思考】请写出实现例3.4算法用栈结构实现的思路。答：栈结构实现思路：处理进栈、出栈、计算及保存之间的逻辑关系。3.9队列应用【例3.5】利用优先队列实现对操作系统进程调度：优先级高的进程先获得CPU，相同优先级的进程先到先获得CPU。思路：（1）初始化1个空优先队列；（2）将若干进程入队；（3）进程出队，直到队列空。代码见应用3.53.9队列应用【进一步思考】优先队列在Java语言中对应的类是什么，其内部本质上在做什么？答：优先队列在Java语言中对应的类是java.util.PriorityQueue<E>