如果你正在刷OJ题或者准备面试栈和队列这两兄弟是绝对躲不过去的。很多新手觉得它们太简单背个 LIFO、FIFO 定义就完事结果真上手遇到稍微绕一点的题照样懵。我见过太多人卡在单调队列上也见过不少人明明知道栈的特性写“有效的括号”时还是各种边界错。这篇我挑了三道经典题拆开揉碎讲一遍有效的括号、用栈实现队列、滑动窗口最大值。从易到难把栈的匹配场景、双栈配合、单调队列的窗口维护全覆盖刷完这组你对栈和队列的理解会从“会背概念”变成“真的会用”。不管你是刚开始刷题的校招生还是想补一补数据结构的在职开发这套组合拳都值得完整走一遍。1. 开刷之前先把栈和队列的底层逻辑捋清楚1.1 栈的“后进先出”到底在解决什么问题栈的规矩就一句话后进的先出也就是 LIFO。很多人把这句话背得滚瓜烂熟但题目一换就开始纠结什么时候入栈什么时候出栈为什么这题非用栈不可我建议你先别急着记结论而是把栈理解成一种“回溯机制”。你玩浏览器每点开一个新页面就相当于入栈一次点后退按钮就是把最近入栈的页面弹出去函数调用也是同一个模型main 调用 funcAfuncA 再调用 funcB运行时一路压栈funcB 返回之后控制权自然回到 funcA。这种“最近发生的事情优先处理”的特性就是栈的天然场景。所以刷题的时候你只要看到“匹配”“回溯”“最近的”“嵌套”这类字眼第一反应就应该是栈。括号匹配、表达式求值、HTML 标签校验、编辑器里的撤销操作底层全是这一套逻辑。理解了这一点题目还没看你心里其实已经有了一个大方向。注意这里不是让你把栈想得多高深恰恰相反栈就是最朴素的“先进后出容器”难点从来不在容器本身而在你什么时候往里面放、什么时候往外拿。1.2 队列的“先进先出”解决的是另一类问题队列正好反过来先进先出FIFO。它的核心价值是“公平”和“顺序”。食堂排队买饭先来的人先打饭后来的人不许插队操作系统里的就绪队列、线程池里的任务队列、分布式系统里的消息队列本质都是同一个模型——谁先到谁先被处理不让任务饿死也不让顺序乱掉。处理这类题主线只有一条队列天然适合“按到达顺序一批一批处理”的场景。不过真正有区分度的题目很少直接考一个裸队列更多是拿双端队列做文章。deque 这个数据结构两端都能进出单调队列就是建立在它上面的高级玩法。很多人一看到 deque 就头大其实它就是一个“前后都能操作”的容器单调队列的核心也不在数据结构本身而是你需要维护一种“窗口内候选答案”的顺序。后面第三题我会专门展开你耐心往下看。1.3 三道题的难度梯度为什么这么排先说结论这组题目是刻意按“会用栈——理解栈和队列的关系——自己改造队列”的路径来排的。第一题“有效的括号”是栈的入门题难度一星考察的是进出栈的时机把握。第二题“用栈实现队列”是进阶题难度两星考察两个抽象数据结构之间的互相实现顺带让你体会均摊分析。第三题“滑动窗口最大值”是经典的单调队列题难度三星属于能在面试里拉开差距的类型。很多人刷题喜欢专挑难题我的建议恰恰相反。这三道题形成一条完整的学习链每一步都正好踩在下一个知识点的台阶上。第一题让你建立“什么时候入栈”的直觉第二题让你明白“栈和队列可以互相转换”第三题逼你跳出固定结构去思考“如何用双端队列维护动态窗口”。刷完再回头看你会发现栈和队列不再是两个孤立概念而是一套思维工具箱。2. 第一题有效的括号栈最经典的开胃菜2.1 题目本身讲的是什么题目很直白给你一个只包含( ) [ ] { }的字符串判断括号是否合法。“合法”包含两层意思第一左右括号数量必须对得上第二嵌套顺序必须正确。比如()合法()[]{}合法({[]})也合法但是([)]就是典型的反例——每个括号都有配对的另一半可顺序错了最内层的[被)隔开了所以不合法。这个题目在 LeetCode 上是 20 号题很多学校的 OJ 也有原题变体。它看起来简单实际上非常考验你对栈进出时机的把握。我见过不少同学能写出能跑的版本但问一句“为什么这里要先判空再取栈顶”就答不上来了。这恰恰是面试官最在意的点。2.2 为什么这道题天然就该用栈核心原因在“匹配顺序”四个字上。一个合法的括号串右括号永远匹配的是它左边最近的那个未匹配左括号。这个“最近优先匹配”的规则和栈的后进先出完全一致。你可以想象剥洋葱或者拆套娃最里面的那层一定最先闭合。比如({[]})遍历到]时最近未匹配的左括号是[正好配对配对成功之后[被处理掉下一层最近未匹配的左括号变成了{再往后是(。整个过程就是不断把“最近来的左括号”弹出栈。所以算法的骨架非常清晰遇到左括号就压栈遇到右括号就去看栈顶是不是对应的左括号是就弹出去不是就说明顺序错了。2.3 完整代码和关键细节给你一份简洁的 C 实现class Solution { public: bool isValid(string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top () || (c ] top [) || (c } top {)) { st.pop(); } else { return false; } } } return st.empty(); } };代码只有十几行但有两个细节值得注意。细节一遇到右括号先判st.empty()。这个很多人会漏掉如果字符串开头就是)此时栈是空的直接取st.top()就是未定义行为程序可能直接崩溃。细节二返回值是st.empty()而不是true。如果输入是(遍历完栈里还压着一个左括号说明没有配对成功这时候必须返回false。如果你想写得再优雅一点可以用哈希表把括号对存起来减少 if 判断class Solution { public: bool isValid(string s) { unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; stackchar st; for (char c : s) { if (pairs.count(c)) { if (st.empty() || st.top() ! pairs[c]) return false; st.pop(); } else { st.push(c); } } return st.empty(); } };2.4 实测下来最容易翻车的三个细节第一只统计数量不校验顺序。有些同学用计数器分别统计三种括号的数量最后看是否相等。这种写法过不了([)]这种用例三个括号数量都匹配但顺序完全不对。第二忘记检查栈是否为空。第三把入栈出栈的判断条件写反遇到右括号去压栈遇到左括号去匹配那整个逻辑就颠倒了。我建议你写完代码后至少跑四个用例(){}[]、([)]、(、)}覆盖正常路径、错误顺序、左括号残留、右括号开头这四种情况基本就能把边界问题堵死。3. 第二题用栈实现队列双栈倒腾出 FIFO3.1 题目要求和它真正的考点这道题在 LeetCode 上是 232 号题要求你只用两个栈来实现一个队列需要支持推入元素push、弹出队首pop、查看队首peek、判断是否为空empty四个操作。表面上看栈和队列的顺序正好相反一个后进先出、一个先进先出怎么可能互相实现但实际是可以的而且巧妙得很——核心就一句话把元素倒腾两次逆序就变回正序了。这道题的高频考点不是你能不能想出双栈方案而是你能不能讲清楚“为什么均摊复杂度是 O(1)”。很多候选人能写出代码一说到复杂度就含糊这题就白刷了。3.2 双栈思路输入栈负责进输出栈负责出两个栈分工很明确inStack专门接收push进来的元素模拟队列的“尾部”。outStack专门负责pop和peek模拟队列的“头部”。关键操作在pop和peek之前如果outStack是空的就把inStack里的元素全部倒进outStack。注意是“全部倒过去”因为只有全部倒过去最先进入inStack的元素才会跑到outStack的栈顶变成队首。举个具体例子。按顺序push(1), push(2), push(3)此时inStack从栈底到栈顶是[1, 2, 3]。执行pop()时把inStack全部倒入outStackoutStack从栈底到栈顶变成[3, 2, 1]。此时outStack的栈顶是1正是最早入队的元素。这个 1 弹出后下一个队首2也自然在outStack栈顶。整个过程就像把一叠文件倒扣过来再拿顺序正好正回来了。3.3 为什么均摊复杂度是 O(1)这是这道题最值得研究的点。如果每次pop都把inStack里的元素全部搬到outStack单次操作的复杂度可能是 O(n)那整体是不是 O(n²)不是。关键在于每个元素被移动的次数是固定的。元素从push进inStack到被pop出outStack最多经历一次“搬运”——就是那一次整体倒腾。之后它就一直待在outStack里直到被弹出。所以 n 个元素总共的搬运次数是 O(n)平均到 n 次操作上每次是常数级的 O(1)。这就是均摊分析的思想不纠结某一次的最坏情况而是看长期多次操作后的平均成本。面试的时候这个“每个元素至多搬一次”的说法很加分比简单背一句“均摊 O(1)”有说服力得多。3.4 可直接参考的代码实现class MyQueue { private: stackint inStack; stackint outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { transfer(); int top outStack.top(); outStack.pop(); return top; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这里有个细节很容易踩坑peek和pop里都要调用transfer()不能只在pop里调用。否则连续调用peek()两次第二次可能拿到错误结果因为outStack没有正确初始化。另外transfer()里的判断条件if (outStack.empty())也很关键。如果outStack还有元素就不能倒否则新倒进来的元素会堆在旧元素下面队首顺序就乱了。这个条件保证“倒腾动作只在输出栈空的时候发生”。3.5 延伸思考反过来用队列实现栈这题熟了之后建议你做一下对称题目用队列实现栈也就是 LeetCode 225 号题。思路不太一样用队列模拟栈可以在push时做文章入队后把前面的元素依次移到后面让新元素跑到队首。这两道题一起刷你对“容器只是工具顺序才是本质”这句话会有特别深的体会。很多面试官喜欢在这之后追问“还能不能用其他方式”如果你能把对称实现也答出来印象分会高出不少。4. 第三题滑动窗口最大值单调队列才是一道分水岭4.1 题目长什么样为什么暴力解法会超时题目描述很常见给一个整数数组nums和一个窗口大小k窗口从数组最左端滑动到最右端每次滑动一格要求返回每次窗口内元素的最大值。比如nums [1,3,-1,-3,5,3,6,7]窗口大小为3结果就是[3,3,5,5,6,7]。这是 LeetCode 239 号题也是单调队列的招牌题。最容易想到的解法是暴力对每个窗口都遍历一遍找到最大值时间复杂度 O(n×k)。如果数组长度是一万窗口大小是五千这就得跑上亿次肯定超时。优化的难点在于窗口每滑动一次只会移出一个元素、新增一个元素大部分旧元素还在窗口里能不能利用上一轮的信息而不是每次都重新扫一遍这就是单调队列登场的原因。4.2 单调队列到底维护的是什么单调队列本质上是一个双端队列里面存的是“窗口内可能是最大值的元素的下标”。它有两个不变量第一个不变量队列里的元素对应数值从队首到队尾严格递减或者非递增。第二个不变量队首下标一定在当前窗口范围内。这样设计之后窗口内当前最大值就是队首元素取出来直接用就行。但维护这两个不变量需要三步操作顺序不能乱。第一步清理过期元素。窗口滑动后队首元素的下标如果小于i - k 1说明它已经滑出窗口了直接pop_front。第二步维护单调性。新元素要从队尾入队但入队之前先把队尾所有小于等于它的元素全部pop_back。为什么要全弹掉因为这些元素既比新元素小又比新元素更早过期它们在后续任何时刻都不可能成为窗口最大值留着纯属浪费空间。第三步把当前下标压入队尾。做完这一步再判断窗口是否已经形成下标到达k-1之后如果形成了就把队首对应的值加入答案。4.3 完整代码与实现细节class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; vectorint result; for (int i 0; i nums.size(); i) { // 1. 清理窗口外的元素 if (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } // 2. 从队尾弹出所有不大于当前元素的索引 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 3. 当前索引入队 dq.push_back(i); // 4. 窗口形成后开始记录 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; } };我特别提醒一个容易写错的位置清理过期元素的判断用的是dq.front() i - k 1不是。因为窗口左边界正好是i - k 1下标等于i - k 1的元素还在窗口内只有小于它才该被移除。这个边界写错结果会莫名少一个最大值。第二个容易翻车的地方是第二步用还是。这里用是为了让重复元素中更靠右的那个留下。比如窗口里有两个相同的最大值如果只弹小于的旧的最大值下标一直在队首等它过期前需要多经历几次pop_front逻辑也能跑通但如果你想让自己更省心就按照“弹出所有小于等于当前值的”来写留下来的永远是更靠后的那个对后续处理更友好。4.4 复杂度分析和为什么用双端队列时间复杂度 O(n)因为每个元素最多入队一次、出队一次。空间复杂度 O(k)因为队列里最多同时存在 k 个下标。这个复杂度几乎是这类“滑动窗口最值”问题的最优解。为什么必须用双端队列而不是普通队列因为普通队列只能在队尾入队、队首出队没法从队尾把较小的元素淘汰掉。你会发现单调队列的操作模式是“队首出队、队尾入队、队尾也可以出队”这是一般队列给不了的能力只有 deque 能同时支持两端操作。这也是为什么我在 1.2 里强调别把队列理解成死板的“一头进另一头出”deque 才是很多高级算法的真正底座。5. 刷题过程中最容易踩的坑和排查思路5.1 三道题的高频错误速查把三道题的坑汇总一下刷题前过一眼能省不少调试时间。题目高频错误排查要点有效的括号忘记判空直接取栈顶遇到右括号先判st.empty()有效的括号最后返回true改为返回st.empty()检查残留用栈实现队列只在pop里转移peek不转移peek和pop都要先调transfer()用栈实现队列转移条件写错必须是输出栈为空时才搬运滑动窗口最大值过期下标判断用了窗口左边界是i - k 1等于号属于窗口内滑动窗口最大值队列里存了值而不是下标存下标才能判断是否过期5.2 我的排查习惯先想清楚“不变式”调这类题我觉得最有效的方法不是到处打印日志而是先问自己一个问题这个数据结构在每一步之间保持了哪些不变式有效括号的不变式是“栈里只存未匹配的左括号栈顶永远是最近的一个”双栈队列的不变式是“输出栈不为空时队首就是输出栈栈顶”单调队列的不变式是“队列单调递减且队首在窗口内”。一旦你把不变式写出来对照代码走一遍样例出错的位置基本一眼就能找出来。这是我从刷题到工作都一直用的调试策略比盲目加打印强太多。5.3 做完之后怎么检验自己真的懂了我自己的习惯是刷完一道题立刻做三件事。第一不看代码在纸上把核心流程的画出来能画出来才算理解。第二换一个边界用例跑一遍比如窗口大小等于数组长度、数组长度等于 1、括号字符串长度为 1 这类极端情况。第三把题目改一个条件再做一次比如有效括号的题目改成允许*通配符用栈实现队列改成用队列实现栈。这三步做完你基本就把一道题吃透了比狂刷十道新题有用得多。6. 从 OJ 到工程这三道题的能力到底迁移到哪里6.1 栈在真实系统里的几个熟人括号匹配看着像玩具但它的思想在真实工程里到处都是。编译器和解释器做表达式求值、做语法分析时抽象语法树和括号匹配是一套底层逻辑HTML 和 XML 的标签嵌套校验本质就是输入一个div就压栈遇到/div就出栈并比对编辑器里的撤销重做用两个栈互相倒腾和双栈实现队列简直是同一个套路。函数调用栈就更不用说了递归程序为什么不能无限递归因为运行时栈有大小限制这就是工程里“栈溢出”的本源。所以面试官问“栈空间不足怎么办、递归调用太深怎么办”其实都是在考察你对“栈是有限资源”的理解。6.2 队列在工程里的存在感更强队列在工程里几乎是无处不在的。后端系统里的消息队列解决的是多个服务之间的异步解耦问题数据库连接池、线程池里的等待队列解决的是资源排队的问题再比如日志系统、任务调度系统底层全是队列模型。哪怕你不写后端前端的事件循环里也有一个任务队列。理解了 FIFO你就理解了“顺序”和“公平”在现代系统设计里为什么重要。单调队列的思想迁移到工程里最典型的场景就是“连续时间窗口内的统计问题”比如限制器里统计最近一分钟的请求数或者传感器数据处理里找滑动窗口内的峰值。这些场景虽然不会让你直接手写单调队列但“保留候选集、淘汰不可能成为答案的元素”这个思路是相通的。6.3 面试时怎么把这些理解讲出来如果你正在准备面试我给你一个表达框架先说暴力思路再说怎么优化最后说复杂度。比如第三题你可以说“暴力每步扫描窗口是 O(n×k)我想到维护一个单调递减的双端队列让队首永远是当前窗口最大值每个元素进出队列各一次所以是 O(n)”。这个回答把思考过程、数据选择、复杂度一次讲清楚面试官基本就不会再追问了。但有一点要提醒面试官最怕的不是你不会而是你背题。如果你能把“为什么用栈”“为什么用 deque”“为什么均摊 O(1)”都讲明白哪怕代码一时没写对也远比把答案背得滚瓜烂熟要强。这三道题我前前后后带过不少同学刷也看他们在真实面试里用过说句实在话能把“有效的括号”讲透的人比能默写“滑动窗口最大值”全代码的人更少见。数据结构不是背模板而是训练你把问题抽象成“操作顺序”的能力。栈和队列只是第一批工具后面的堆、哈希表、树全是一样的学法。刷题这事没有捷径但有高效路径——先把每一道经典题吃透再谈量变引起质变。