教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本篇技术指南围绕 YCBlogs 仓库 leetcode/03.栈 系列中「栈的压入、弹出序列」这道经典算法题展开讲解如何借助一个辅助栈判断给定的弹出序列是否合法完整覆盖题目约束、模拟思路、手工推演、可运行的 Java 代码与复杂度分析并结合仓库内栈基础、JDKStack源码等系列笔记做纵深佐证。读完本文你将掌握「辅助栈模拟法」这类栈仿真问题的通用套路能独立写出面试级别的判定代码并理解其正确性边界。01. 题目要求输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。注意这两个序列的长度是相等的。这是剑指 Offer 中的经典题目在 11.栈的压入、弹出序列.md 中有完整记录核心难点在于弹出动作可以发生在任意次压入之后因此无法直接通过「元素在弹出序列中的相对位置」做简单判断必须按过程进行仿真。02. 问题分析借辅助栈模拟压入弹出全过程2.1 核心思路【思路】借用一个辅助栈s按顺序遍历压栈序列执行以下两步每遇到一个压入元素先将其push进辅助栈然后循环检查只要辅助栈栈顶元素等于弹出序列当前指向的元素就立即出栈并将弹出序列指针向后移动一位直到栈顶不匹配为止。压入序列遍历完毕后若辅助栈仍不为空说明弹出序列不是该栈的弹出顺序。这里的关键在于弹出序列决定的是「何时可以弹出」而辅助栈则忠实还原了真实栈中元素的进出次序。每一次匹配成功都等价于在真实的压入/弹出过程中完成了一次合法的出栈。2.2 手工推演举例以入栈1,2,3,4,5、出栈4,5,3,2,1为例完整推演过程如下入栈 1,2,3,4,5 出栈 4,5,3,2,1 首先 1 入辅助栈此时栈顶 1 ≠ 4继续入栈 2 此时栈顶 2 ≠ 4继续入栈 3 此时栈顶 3 ≠ 4继续入栈 4 此时栈顶 4 4出栈 4弹出序列向后一位此时为 5辅助栈里面是 1,2,3 此时栈顶 3 ≠ 5继续入栈 5 此时栈顶 5 5出栈 5弹出序列向后一位此时为 3辅助栈里面是 1,2,3 依次执行最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。可以这样理解辅助栈内的元素永远保持「压入过、但尚未被弹出序列消费」的状态当辅助栈最终为空说明弹出序列恰好把压入序列中的所有元素都按合法顺序消费完毕二者一一对应判定为合法。03. 实例代码与逐行解析仓库中给出的参考实现如下原始出处为牛客网剑指 Offer 讨论区的思路代码完整保留在 11.栈的压入、弹出序列.md 中public class Solution { public boolean IsPopOrder(int [] pushA, int [] popA) { if (pushA.length 0 || popA.length 0) return false; StackInteger s new StackInteger(); // 用于标识弹出序列的位置 int popIndex 0; for (int i 0; i pushA.length; i) { s.push(pushA[i]); // 如果栈不为空且栈顶元素等于弹出序列 while (!s.empty() s.peek() popA[popIndex]) { // 出栈 s.pop(); // 弹出序列向后一位 popIndex; } } return s.empty(); } }3.1 关键点一popIndex指针popIndex是指向弹出序列popA当前待匹配位置的指针初始为0。每当辅助栈栈顶与popA[popIndex]相等并出栈一次popIndex就自增一次。它的存在把「弹出序列还剩哪些元素没被消费」显式地表达出来是整个算法的核心状态。3.2 关键点二内层while而非if内层循环必须使用while因为一次压入后栈顶可能连续多次与弹出序列匹配例如上面例子中压入5后5、3、2、1连续出栈。若只用if每次压入只能匹配一次就会漏掉连续弹出的合法情况导致结果错误。3.3 关键点三防御性边界判断if (pushA.length 0 || popA.length 0) return false;当两个序列任一为空时直接返回false。需要说明的是这是本实现的一种约定有的题解对两个空序列返回true实际面试中可以和面试官明确约定空输入的处理语义代码行为取决于该约定。3.4 关于popIndex不会越界的说明一个值得推敲的细节是内层while中出现了popA[popIndex]为什么不会发生数组越界原因在于——popA每被消费一个元素辅助栈中就少一个元素若popIndex已经推进到popA.length说明n个元素全部被弹出消费此时辅助栈必然为空!s.empty()条件为假循环自然不会再进入。因此popIndex的有效访问范围始终有保证这也是「两序列长度相等 数字互不相等」约束下的必然结果。04. 反例推演为什么 4,3,5,1,2 不合法用同一套代码逻辑验证题目给出的反例4,3,5,1,2压入序列1,2,3,4,5 弹出序列4,3,5,1,2 i0压入 1栈顶 1 ≠ 4 i1压入 2栈顶 2 ≠ 4 i2压入 3栈顶 3 ≠ 4 i3压入 4栈顶 4 4 → 出栈popIndex1指向 3 栈顶 3 3 → 出栈popIndex2指向 5 栈顶 2 ≠ 5内层循环停止 i4压入 5栈顶 5 5 → 出栈popIndex3指向 1 栈顶 2 ≠ 1内层循环停止 压入序列遍历完毕辅助栈中残留 [1,2]不为空 → 返回 false直观解释当4、3弹出后5弹出前栈中剩余1,2而5尚未入栈等5入栈并弹出后栈顶是2但弹出序列要求下一个弹出的是1——1被2压在下面无法在不违反 LIFO 规则的前提下先于2弹出因此该序列不合法。05. 复杂度分析时间复杂度O(n)。压入序列中的每个元素至多被push一次、至多被pop一次内外两层循环的总执行次数与元素个数成正比因此整体是线性时间。空间复杂度O(n)。最坏情况下例如弹出序列要求所有元素在压入完成后才依次弹出辅助栈需要容纳全部n个元素。这与仓库中 00.栈的基础介绍.md 对栈基本操作「入栈、出栈时间复杂度均为常数 O(1)不依赖栈中数据项个数」的结论一致因为每次匹配都只读栈顶peek而不做查找所以整体才能保持线性。06. 回到基础YCBlogs 栈系列的知识支撑本题的全部推理都建立在「栈是先进后出FILO的受限线性表」这一基本性质之上仓库中 leetcode/03.栈 系列从多个角度为这个结论提供了佐证6.1 栈的基本特性00.栈的基础介绍.md 指出栈是一端受限、一端允许操作的线性表即「先放的后取后放的先取」典型场景包括网页浏览历史后退、文档编辑器的撤销序列、Android 中 Activity 与 Fragment 的栈管理。本题之所以要「借辅助栈模拟」正是因为弹出顺序受限于这一 LIFO 约束任何不满足约束的弹出序列都无法被真实栈复现。6.2 JDKStack的底层实现01.栈的实现原理.md 展示了 JDK 源码StackE extends VectorE底层用数组实现push(E item)调用addElement(item)即数组末尾追加pop()先peek()取栈顶再removeElementAt(len - 1)删除peek()在栈空时抛出EmptyStackException相关方法使用synchronized修饰保证线程安全。这解释了本题代码中StackInteger s new StackInteger()的语义它就是教科书「顺序栈」的 JDK 封装peek()只读栈顶不移除pop()弹出并移除empty()判空——正是推演过程需要的全部操作。6.3 系列内的同类经典题05.用两个栈实现队列.md利用两个栈「负负得正」地完成队列的Push/Pop与本题同属「模拟数据结构行为」的栈应用题二者互为镜像——本题判断一个序列能否由栈产生该题则用栈去实现队列语义。06.栈实现浏览器进退.md用栈 X、栈 Y 模拟浏览器的前进后退原理是「后进先出」的历史回退进一步印证了「双栈/辅助栈」在工程场景中的实际价值。15.使用栈判断括号是否匹配.md同样是「扫描序列 栈顶匹配」的模式只是匹配规则从「栈顶等于弹出元素」变为「左右括号配对」。这些题目与本篇共用同一套方法论用一个栈忠实记录状态用序列驱动栈的进出最终以栈的状态判定合法性。整套栈系列笔记的索引见 06.算法大汇总.md 的「03.栈」一节。07. 小结「栈的压入、弹出序列」是一道非常典型的栈仿真类问题值得记住的要点有三辅助栈模拟严格按压入顺序入栈一旦栈顶与弹出序列当前元素匹配就立即弹出并用popIndex追踪弹出序列的消费进度匹配用while一次压入可能触发连续多次弹出必须循环匹配最终判空压入序列遍历完后辅助栈为空则弹出序列合法否则不合法。整体时间复杂度 O(n)、空间复杂度 O(n)是面试中「最优解」级别的标准答案掌握这道题也就掌握了括号匹配、双栈实现队列等一系列栈模拟题目的共同解法。更完整的栈知识体系基础特性、顺序/链式实现、JDK 源码分析、系列算法题可继续阅读仓库 leetcode/03.栈 目录下的全部系列文档。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐栈的压入、弹出序列判定LeetCode-Book 中《剑指 Offer 31》的辅助栈模拟法与三语言实现栈的压入、弹出序列判定LeetCode Book 中《剑指 Offer 31》的辅助栈模拟法与三语言实现 本篇技术指南围绕 LeetCode Book 仓库中示例工程剑指 Offer 31 栈的压入、弹出序列:用模拟栈判定弹出顺序的完整实现与复杂度分析剑指 Offer 31 栈的压入、弹出序列:用模拟栈判定弹出顺序的完整实现与复杂度分析 本文基于 CS Notes 仓库中的剑指 Offer 题解文档 31.知识库文档教程栈的压入弹出序列GitHub_Trending/le/LeetCode-Book模拟验证法栈的压入弹出序列GitHub_Trending/le/LeetCode Book模拟验证法 痛点解析如何判断栈操作的合法性 你是否曾在面试中遇到这样的问题示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考