企业官网建设流程全解析

如果你正在刷OJ题或者准备面试，栈和队列这两兄弟是绝对躲不过去的。很多新手觉得它们太简单，背个 LIFO、FIFO 定义就完事，结果真上手遇到稍微绕一点的题照样懵。我见过太多人卡在单调队列上，也见过不少人明明知道栈的特性，写“有效的括号”时还是各种边界错。这篇我挑了三道经典题拆开揉碎讲一遍：有效的括号、用栈实现队列、滑动窗口最大值。从易到难，把栈的匹配场景、双栈配合、单调队列的窗口维护全覆盖，刷完这组，你对栈和队列的理解会从“会背概念”变成“真的会用”。不管你是刚开始刷题的校招生，还是想补一补数据结构的在职开发，这套组合拳都值得完整走一遍。

1. 开刷之前，先把栈和队列的底层逻辑捋清楚

1.1 栈的“后进先出”到底在解决什么问题

栈的规矩就一句话：后进的先出，也就是 LIFO。很多人把这句话背得滚瓜烂熟，但题目一换就开始纠结：什么时候入栈？什么时候出栈？为什么这题非用栈不可？我建议你先别急着记结论，而是把栈理解成一种“回溯机制”。你玩浏览器，每点开一个新页面就相当于入栈一次，点后退按钮就是把最近入栈的页面弹出去；函数调用也是同一个模型，main 调用 funcA，funcA 再调用 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) { stack<char> 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_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; stack<char> 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. 第二题：用栈实现队列，双栈倒腾出 FIFO

3.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全部倒入outStack，outStack从栈底到栈顶变成[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: stack<int> inStack; stack<int> 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: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> 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 三道题的高频错误速查

把三道题的坑汇总一下，刷题前过一眼，能省不少调试时间。

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)”都讲明白，哪怕代码一时没写对，也远比把答案背得滚瓜烂熟要强。

这三道题我前前后后带过不少同学刷，也看他们在真实面试里用过，说句实在话，能把“有效的括号”讲透的人，比能默写“滑动窗口最大值”全代码的人更少见。数据结构不是背模板，而是训练你把问题抽象成“操作顺序”的能力。栈和队列只是第一批工具，后面的堆、哈希表、树，全是一样的学法。刷题这事没有捷径，但有高效路径——先把每一道经典题吃透，再谈量变引起质变。