企业官网建设流程全解析

栈和队列这一组题，可以说是算法刷题路上最“亲民”的专题了。Day9我选了LC 232、LC 225、LC 20、LC 1047这四道，两题是栈与队列的互实现，两题是栈的经典应用场景。很多刚开始刷算法的人会忽略这个专题，觉得“容器不是直接用就行了吗”，但实际上这四道题能把“逻辑结构”和“底层存储”这两个概念彻底掰开揉碎——栈和队列的代码实现极其简单，但背后涉及的操作约束、接口设计、复杂度摊还分析，全是面试和竞赛里高频出现的考察点。

这篇文章作为一个补档记录，我会把这四道题的完整思路、手写代码、踩坑细节和延伸场景都写清楚。不论你是准备面试、打竞赛，还是单纯想复健数据结构，这份笔记都能直接拿来用。

1. 为什么拿栈和队列开刀：半天刷四道题的复健逻辑

1.1 复健第一天的选题标准

停刷算法大概半年之后重新捡起来，我给自己定的规则很简单：不求难、不求新，先把最基础的数据结构重过一遍。数组、链表、栈、队列、哈希表、树，这些是后续一切题型的“底座”。栈和队列看起来简单，但很多人对它们的理解停留在“会用STL”的层面，真让你手写一个模拟结构，或者分析一段代码的复杂度，反而容易卡住。

我选这四道题的标准有三个：

• 题目短小精悍，适合作为一天内的集中训练。
• 前两题是“互相实现”，能强迫你从行为层面理解两种结构，而不只是背API。
• 后两题是“栈的应用”，能把栈的特性和真实场景（括号匹配、相邻消除）对应起来。

复健阶段不要贪多，一天一个专题、每个专题四道题，节奏刚刚好。刷完之后你会发现，后面做到二叉树遍历、单调栈、表达式求值这些题，其实都在反复用到今天这四道题的思想。

1.2 这四道题为什么要一起刷

把这四道题放在一起，不是说它们难度相当，而是它们之间有一条完整的逻辑链：

1. 你需要知道“栈”长什么样（LIFO），才能用栈去模拟队列（FIFO）。
2. 你需要知道“队列”长什么样（FIFO），才能用队列去模拟栈（LIFO）。
3. 你需要理解栈的“最近匹配”特性，才能用它处理括号。
4. 你需要理解栈的“撤销回退”特性，才能用它消除相邻重复项。

这四条串起来，你对栈和队列的理解就不是背概念了，而是“在什么场景下，这类结构天然能解决什么问题”。这个认知比会写几道题重要得多。

1.3 刷前必补的最小知识：栈和队列的底层差异

在开始敲代码之前，先明确两组核心差异，后面对话都基于这两个点：

从C++的角度看，std::stack和std::queue都是容器适配器（container adapter），它们默认基于std::deque实现，但你可以指定底层容器，比如std::stack<int, std::vector<int>>。这是STL的设计哲学：逻辑接口和底层存储解耦。这也解释了为什么LeetCode上存在“用队列实现栈”这种题——底层存储一样，逻辑行为不同，你完全可以靠自己翻出想要的行为。

2. LC 232 用栈实现队列：双栈翻转是在给操作“记账”

2.1 核心解法：输入栈和输出栈的分工

题目要求你用两个栈实现一个先入先出的队列，支持push、pop、peek、empty四种操作。

我用两个栈来解决问题：

• stackIn负责接收新元素，所有push直接进它。
• stackOut负责输出元素，所有pop和peek都从它取。

关键机制是：当stackOut为空时，把stackIn里的元素全部倒进stackOut。因为栈是LIFO，倒一遍之后，stackIn的栈底元素会变成stackOut的栈顶元素，正好等效于队列的队头。

代码实现：

class MyQueue { private: stack<int> stackIn; stack<int> stackOut; void transfer() { if (!stackOut.empty()) return; while (!stackIn.empty()) { stackOut.push(stackIn.top()); stackIn.pop(); } } public: void push(int x) { stackIn.push(x); } int pop() { transfer(); int top = stackOut.top(); stackOut.pop(); return top; } int peek() { transfer(); return stackOut.top(); } bool empty() { return stackIn.empty() && stackOut.empty(); } };

2.2 摊还复杂度到底怎么算

这题面试官最喜欢的追问是“复杂度是多少”。如果你只回答“push是O(1)，pop是O(n)”，会被追问“为什么均摊下来是O(1)”。

摊还分析的关键是：每个元素最多只会经历一次“从stackIn到stackOut”的搬运。元素1进栈、元素2进栈、元素3进栈，只有当你要pop的时候才触发一次搬运，把1、2、3一起倒过去。之后连续的pop都是O(1)直接出栈。所以整个生命周期里，每个元素被push一次、被transfer一次、被pop一次，总操作数大约是3n，均摊到每次操作就是O(1)。

用个生活化的类比：你把一箱书从书桌搬进书架（push），当别人跟你要书时，你一次性把整箱书从书架搬到书桌上（transfer），之后连续取书都是直接拿，不用再去书架翻了。这比你每要一本书就跑一趟书架高效得多。

2.3 踩坑记录：peek的复用与transfer的重复调用

我写第一版代码的时候，pop和peek各写了一遍搬移逻辑，结果就是代码拖沓且容易出错。后面改成提取一个transfer()方法，在pop和peek里先调用它，逻辑就清爽了。

有个细节值得注意：peek()可以直接调pop()再push回去吗？可以，但没必要，因为这样会改变队列顺序吗？不会，pop()取出的是队头，push回去也是放到队尾，顺序保持不变。但这样做有两个问题：一是多了一次入栈出栈，二是把“读”操作变成了“写”操作，语义上不够清晰。我更推荐单独写peek()，里面只做读取和搬移。

2.4 这题翻车最多的边界场景

• 在空队列上执行pop()或peek()：stackOut和stackIn都为空时调用transfer()不会有问题，但后续访问stackOut.top()就是未定义行为。所以实际使用前要判断empty()，题目测试数据一般不会让你违规操作，但自己写代码时要有防御意识。
• 连续peek不会触发重复搬运：因为transfer()会先检查stackOut是否为空，非空就直接返回。
• empty()不能只看一个栈：如果只查stackIn，当stackOut里还有积压元素时你会误判队列为空。必须两个栈都为空。

3. LC 225 用队列实现栈：只用一个队列，关键在入队时做手脚

3.1 核心思路：入队之后重新排队

用队列模拟栈，常见的做法有两种：双队列法和单队列循环法。双队列的写法是很多教科书的标准答案，但实际写下来你会发现，单队列的解法更简洁，也更贴近“队列轮转”的本质。

单队列的核心思想很简单：每次push(x)时，先把x入队，然后把队列前面的所有元素依次出队再入队，这样新元素就会被旋转到队头。此时队头就是栈顶，pop和top都直接看队头。

代码实现：

class MyStack { private: queue<int> q; public: void push(int x) { q.push(x); int size = q.size(); // 把前 size-1 个元素重新入队，让新元素变成队头 for (int i = 0; i < size - 1; i++) { q.push(q.front()); q.pop(); } } int pop() { int top = q.front(); q.pop(); return top; } int top() { return q.front(); } bool empty() { return q.empty(); } };

3.2 复杂度对比：单队列与双队列的取舍

两种方案都能通过题目测试，选择哪一种取决于你希望哪边更快。如果业务场景里入栈操作远多于出栈，双队列法更优；如果出栈操作频繁，单队列法更优。LeetCode题解里还有一种优化思路是用两个队列，但不做搬移，而是维护一个top变量直接记录栈顶，只在pop时轮转，能把top()降为O(1)。这里不展开了，感兴趣可以自己推一下。

3.3 一个容易被忽略的接口：back()

这题里面有一个细节特别容易被忽略：std::queue除了front()之外，还有back()方法，可以直接访问队尾元素。这意味着在只需要“看一眼栈顶”的场景下，你甚至可以不用轮转，直接返回q.back()。

为什么可以？因为我们每次push之后都执行了轮转，新元素永远在队头，front()和back()指向同一个元素。但如果你的实现里没有轮转，而是维护一个top变量，back()的语义就会变——它始终指向最后入队的元素，恰好就是栈顶。C++的queue底层是deque，back()是O(1)，所以直接用是完全可行的。

4. LC 20 有效括号匹配：栈不是唯一方案，但栈是最好写的方案

4.1 匹配问题的本质：最近未匹配的左括号

括号匹配是一道经典中的经典。核心逻辑一句话就能说清：遇到左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号。如果不是，或者栈为空，直接返回false。遍历完整个字符串后，栈必须为空。

为什么这题非要用栈？因为括号匹配的规则是“最近匹配”——[({})]是合法的，[(])是非法的。数组能做到吗？理论上可以，你需要维护“当前还没匹配的左括号序列”，并且始终只跟最后一个比较。这就是栈的定义，所以栈是这个场景的天然选择。

代码实现：

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 != '{')) { return false; } st.pop(); } } return st.empty(); }

4.2 剪枝技巧：长度是奇数，直接返回false

这是我复健时最想分享的一个经验：在进入主逻辑之前，先做一次奇偶校验。如果字符串长度是奇数，那它必然不可能完成匹配，直接返回false。这个剪枝能帮你避免最长的那个测试用例上多跑一遍无用循环，虽然只是O(n)里的一个常数因子，但也是好的编码习惯。

还有一种更简洁的写法：用map存配对关系，遇到右括号时和栈顶比对。但要小心嵌套的场景，比如字符串"{[]}"，你必须在入栈前统一将左括号转成对应的右括号，或者在比较时做映射。两种写法本质上没有区别，选你更顺手的即可。

4.3 边界清单：字符串合法性陷阱

这题的边界条件极其经典，我列一下自己踩过的坑：

• 左括号开头，右括号结尾：这是理想情况，走一遍就过了。
• 右括号开头：比如字符串"}()"，在栈为空时遇到右括号，直接返回false。
• 只有左括号：比如字符串"((("，主循环结束后栈非空，返回false。
• 只有右括号：比如字符串"))"，第一个字符就会被判死，栈为空返回false。
• 空字符串：返回true，这符合常规定义。

还有一类容易错的情况是“交叉匹配”，虽然平时不太会遇到，但一旦测试覆盖到，能直接暴露你对栈的理解是否深入——"([)]"这种就是非法的，因为]匹配的栈顶是(, 不匹配。这类用例是面试时最快的“看人下菜碟”。

5. LC 1047 删除字符串中的所有相邻重复项：用栈顶指针做“记忆回退”

5.1 栈写法第一次成型

题目给一个字符串，要求反复删除相邻且相同的两个字符，直到不能再删。例如"abbaca"经过bb删除变成"aaca"，再删aa变成"ca"，最终返回"ca"。

我第一次做这题时，第一反应是双指针。但仔细想了一下，双指针需要反复从头部重新扫描，因为你删完一组之后，两侧的新字符可能又变成相邻重复项。用栈就不一样了：每来一个字符，就看它和栈顶是否相同，相同就把栈顶弹出，不同就入栈。这个过程天然地处理了“删除后产生新相邻”的情况，因为删除操作等于栈的pop，新暴露出来的栈顶就是删除位置左侧的字符，下一轮循环自然会和它比较。

5.2 用string和tail指针省掉反转

栈的常规写法是：

string removeDuplicates(string s) { stack<char> st; for (char c : s) { if (!st.empty() && st.top() == c) { st.pop(); } else { st.push(c); } } string result; while (!st.empty()) { result += st.top(); st.pop(); } reverse(result.begin(), result.end()); return result; }

这里有个麻烦：最后要把栈里的元素倒出来再反转，因为栈的顺序是反的。有没有办法省掉这一步？有，直接用string的back()和pop_back()模拟栈。string本身就是动态数组，尾部入栈出栈都是O(1)，还省掉了反转。

string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() && result.back() == c) { result.pop_back(); } else { result.push_back(c); } } return result; }

这个写法在很多题解里叫“原地栈”，实际测下来不仅代码更短，执行效率也更高。std::stack默认底层容器是std::deque，它的随机访问和缓存友好性都不如连续的std::string。

5.3 从这题看“栈顶即当前状态”的模型

这题值得多琢磨一层：为什么“删除后产生新相邻”这件事，用栈处理起来这么自然？

我的理解是，栈在这个场景里维护的是一个“当前还没被消除的序列状态”，而栈顶是这个状态里最新需要关注的元素。每次扫描一个新字符，它只可能跟当前状态的最新元素发生关系（相同就消除，不同就追加），所以操作局部性极强——你根本不需要回头看更早的元素，因为它们要么已经被消除，要么不在栈顶就不可能和当前字符直接相邻。这个“栈顶即当前状态”的模型，是后面做单调栈、表达式求值等一系列题的思想基础。

6. 四道题放一起看：栈与队列的本质差异和应用地图

6.1 从互实现到应用：一张脑图理清关系

用文字描述一下我对这四道题关系的理解：

• LC 232 用栈实现队列：LIFO套着FIFO，外部看是队列，内部靠“两次翻转”恢复顺序。
• LC 225 用队列实现栈：FIFO套着LIFO，外部看是栈，内部靠“轮转”改变顺序。
• LC 20 有效括号：栈的“最近匹配”特性直接解决问题。
• LC 1047 删除相邻重复：栈的“回退消除”特性直接解决问题。

如果把四道题按“题目特征”分类，前两题属于“容器行为模拟”，后两题属于“结构特性应用”。前者考验你对接口语义的理解，后者考验你能否把问题抽象成“最近状态匹配”或“相邻消除”。这两类能力都很重要，刷题时不要只追求AC，要刻意区分题目考察的是哪一类。

6.2 从LeetCode到业务代码：栈和队列都在哪儿

有人会觉得，刷题是刷题，工作里根本用不到栈和队列。实际上你每天都在用，只是它们藏在框架和系统底层：

• 函数调用的递归实现，靠的就是调用栈（call stack），栈溢出在系统里对应的是无限递归或栈上超大局部变量。
• 浏览器的前进后退、编辑器的撤销重做，都是典型的栈结构。
• 消息队列是最典型的队列应用，生产者消费者模型、异步任务调度，routing规则再复杂，核心还是FIFO。
• 操作系统的任务队列、阻塞队列、线程池的任务缓冲，本质都是队列，只是加上了并发控制的包装。

面试官问“栈和队列的区别”，真正想听的往往不是定义，而是你能不能把这两个结构映射到真实系统中的角色上。我在实际项目中写过阻塞队列做日志异步落盘，也用递归遍历过树形菜单。这些场景一旦经历过，再看LeetCode里的栈和队列就多了一层“噢，原来这就是通用的模式”的感觉。

6.3 复健Day9的技术收获总结

对我来说，Day9这四道题的价值不在题目本身，而在于几个认知刷新：

第一，“模拟”不是无聊的翻译题。用栈模拟队列、用队列模拟栈，能帮你彻底分清“逻辑行为”和“底层实现”的边界。面试里这个题几乎是必考题，不是因为它有多难，而是因为它是检验基本功的试金石。

第二，栈的“最近性”是一个可以被反复利用的武器。括号匹配和相邻重复消除，一个是“最近对应”，一个是“最近消除”。把这两题做透，再往后看到“计算器求值”、“接雨水”、“每日温度”，你会自然想到单调栈——那只是栈的升级版，核心思想还是“维护一个有序的状态序列”。

第三，代码的简洁性往往来源于对数据结构本质的理解。用string替代stack、用单队列替代双队列，这些优化都不是硬背的技巧，而是理解了“当前状态只跟栈顶有关”之后自己长出来的。

最后，留一道进阶题给看完这篇笔记的人：LC 150 逆波兰表达式求值。它和“删除相邻重复”一样是栈的经典应用，但多了一层运算符优先级和数字解析的逻辑。如果你今天这四道题都能独立写出来，那道题应该也难不住你。Day9的复健记录就到这里。