企业官网建设流程全解析

算法训练营进行到 Day10，终于轮到栈与队列 part01。说实话，很多学员对这个主题的第一反应是“就这？两个线性结构而已”，但真正开始写题之后才发现，栈和队列不是“会不会用”的问题，而是“什么时候入栈、什么时候出栈、什么时候该用队列”的问题。Day10 的内容在代码随想录、各类算法训练营里通常被拆成两到三天的量，part01 主要覆盖：栈和队列的底层实现、用栈实现队列、用队列实现栈、有效括号、删除字符串相邻重复项、逆波兰表达式求值。这篇文章是我带这一期训练营的完整复盘，包含手写实现的细节、踩过的坑、边界条件的处理方式，以及从 Day10 开始应该建立的几个算法习惯。

1. 为什么训练营要把栈和队列单独拿出一天讲

很多人会问：栈和队列不就是两个限定操作方式的容器吗？数组、链表都学了，为什么还要单独花一天。我的回答是：栈和队列在算法题里承担的角色，比看起来重要得多，它不只是容器，更是一种“操作规则”和“思维模式”。

1.1 栈和队列的本质是“操作受限”的线性表

栈和队列底层都可以用数组或链表实现，但它们和普通数组、链表最大的区别是限制了操作位置。栈只能在一端操作，所以是后进先出（LIFO）；队列只能在一端进、另一端出，所以是先进先出（FIFO）。

这个限制不是缺点，反而是解题的核心。很多题目之所以要用栈，不是因为栈存储能力强，而是因为题目本身就存在一种“后到的东西先处理”的顺序。括号匹配就是典型：最后一个左括号要最先被匹配，这就是 LIFO；而树的层序遍历、BFS 需要逐层扩展，先到的节点先处理，这就是 FIFO。

我经常跟学员说，学栈和队列时不要盯着“它们能存什么”，要看“它们的弹出顺序解决了什么问题”。你能在拿到题目的十分钟内说出“这题为什么用栈”“用队列行不行”，Day10 就算过关了。

1.2 从课程安排看 part01 的定位

在大多数算法训练营的路线图里，Day10 之前已经有了数组、链表、哈希表的基础，之后会进入二叉树、回溯、动态规划这些更复杂的主题。栈和队列放在这个节点，是因为它刚好承接了两条线：

• 从数据结构看，栈和队列是线性表的两种特化形式，能帮助你把数组和链表的理解变成“可操作的具体结构”。
• 从算法题看，括号匹配、表达式求值、滑动窗口、单调栈、BFS 都直接建立在栈和队列之上。

part01 通常不深入单调栈和优先队列（堆），而是先把最基础的机制讲透。这样安排的好处是，后面学二叉树迭代遍历时，你看到“用栈模拟递归”不会慌；学图的最短路径时，看到“用队列做 BFS 层级扩展”也不会觉得是全新概念。

1.3 竞赛和工程里，栈和队列到底用得频不频繁

热搜里有一个问题叫“C++ 栈竞赛用的多吗”，我可以直接回答：非常多。竞赛里栈不只是 std::stack，手写数组模拟栈在 DFS、表达式求值、单调栈、括号匹配里到处都是。队列同样，BFS、SPFA、滑动窗口、拓扑排序，都是基于队列跑的。

工程里也一样。函数调用时的调用栈、编辑器里的撤销操作、浏览器的后退页面，本质都是栈。消息队列、阻塞队列、生产者消费者模型，本质都是队列在不同并发场景下的扩展。所以这不是一个“学完就扔”的基础知识，它会在后续所有环节反复出现。

2. 栈与队列手写实现：先把地基打牢

Day10 第一部分，我强烈建议每个学员都手写一遍栈和队列，而不是只调 STL。原因很简单：手写一次之后，你才会真正理解“栈顶指针”“队头队尾指针”“循环队列判空判满”这些概念，后面 Debug 时也更容易看出来问题。

2.1 用数组模拟栈：为什么竞赛里常这么干

C++ 里用 std::stack 当然可以，但竞赛和高频刷题场景下，很多人选择用数组模拟：

const int N = 100010; int stk[N]; int top = 0; // 指向栈顶元素的下一个位置 void push(int x) { stk[top++] = x; } void pop() { if (top > 0) top--; } bool empty() { return top == 0; } int peek() { return stk[top - 1]; }

这里的关键设计是 top 的语义。我习惯让 top 指向“下一个可写入位置”，初始为 0。那么栈为空的条件就是 top == 0，栈顶元素是 stk[top - 1]。如果你想让 top 指向栈顶元素本身，初始化为 -1，那 push 要写成 stk[++top] = x。两种写法都能工作，但混用就会出问题。

用数组模拟的好处有三个：第一，常数小，没有 STL 的封装开销；第二，调试时可以 printf 整个 stk 数组，看到栈的全貌，而 std::stack 只能看到顶；第三，可以为后面手写单调栈、手写递归模拟打基础。LeetCode 刷题时用 vector 模拟栈也很方便，push_back 和 pop_back 就行。

2.2 循环队列：判空判满的三种方案

队列的手写实现比栈多一个容易踩坑的地方：循环队列。先看一段基础实现：

const int N = 100010; int q[N]; int head = 0, tail = 0; // head 指向队头，tail 指向队尾下一个位置 void push(int x) { q[tail++] = x; if (tail == N) tail = 0; } void pop() { if (head != tail) { head++; if (head == N) head = 0; } }

这个实现有个致命问题：当 head == tail 时，可能是空，也可能是满。因为 tail 绕一圈之后又追上了 head，空和满的状态无法区分。

解决思路有三招：用 size 计数、留一个空位、用 flag 标记。

• 用 size 计数最直观：push 时 size++，pop 时 size--，判空 size == 0，判满 size == N。
• 留一个空位是竞赛常用写法：初始化 head = 0，tail = 0；判空 head == tail，判满 (tail + 1) % N == head。这意味着数组最多存 N - 1 个元素。
• 用 flag 标记也能区分，但代码略绕，日常刷题用得少。

很多学员觉得循环队列麻烦，直接用 std::queue 就行。确实，LeetCode 基础题用 STL 没问题，但理解循环队列对后续 BFS、滑动窗口、手写阻塞队列都很有帮助。BFS 里队列不断入队出队，如果你心里清楚 head 和 tail 是怎么移动的，就不会对“为什么 queue 能自动释放”感到疑惑。

2.3 用栈实现队列、用队列实现栈：互为逆操作的经典题

这两道题是 Day10 必做中的必做。它们不考复杂的算法，考的是对数据结构操作顺序的理解。

用两个栈实现队列（LeetCode 232）的核心思路：

class MyQueue { private: stack<int> stIn; stack<int> stOut; public: void push(int x) { stIn.push(x); } int pop() { if (stOut.empty()) { while (!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } } int res = stOut.top(); stOut.pop(); return res; } int peek() { int res = this->pop(); stOut.push(res); return res; } bool empty() { return stIn.empty() && stOut.empty(); } };

关键在于：只有在 stOut 为空时，才把 stIn 的全部元素倒进去。这样做是为了保证元素在 stOut 里的顺序正好是队列顺序。如果每次 push 都倒一次，复杂度会变得不稳定；只在需要 pop 且 stOut 为空时倒，每个元素最多被移动两次，均摊时间复杂度就是 O(1)。

用两个队列实现栈（LeetCode 225）则要反过来想。栈顶是最后一个进来的元素，所以 pop 时要把前 n - 1 个元素从主队列挪到备用队列，剩下那个就是栈顶。这里有个小细节：C++ 的 std::queue 只有 front，没有 back（deque 才有），所以别指望直接访问队尾。

这两道题做完之后，建议在草稿纸上画一下三个状态的转换：初始空、连续 push、交替 push/pop。只要你能画清楚“数据从哪个容器流向哪个容器，顺序发生了什么变化”，这两题的底层逻辑就彻底掌握了。

3. 三道经典栈应用题：重点不是“用栈”，而是“什么时候弹出”

Day10 的 part01 里通常会配三四道栈的经典题。很多人的误区是：题目一看“括号匹配”，哦用栈；再看“删除相邻重复项”，哦还是用栈；然后就开始套模板。但真正决定代码对错的，是“什么时候入栈、什么时候出栈、栈空时怎么办”。

3.1 有效的括号：相邻匹配问题

LeetCode 20 是栈的入门题。核心逻辑：遍历字符串，遇到左括号时入栈，遇到右括号时检查栈顶是否匹配。

常见的写法有两种：一种是遇到左括号 push 左括号，遇到右括号时比较栈顶；另一种是遇到左括号时 push 对应的右括号，遇到右括号时直接和栈顶比较。我更推荐第二种，因为代码更短，也不容易出现字符串比较的细节错误：

bool isValid(string s) { if (s.size() % 2 == 1) return false; stack<char> st; for (char c : s) { if (c == '(') st.push(')'); else if (c == '[') st.push(']'); else if (c == '{') st.push('}'); else { if (st.empty() || st.top() != c) return false; st.pop(); } } return st.empty(); }

这个写法把三种括号统一成一个逻辑：栈里存的是“期待匹配的右括号”。如果是左括号，就告诉未来：“我期待一个右括号”；如果遇到右括号，就检查当前期待的是不是它。

有几个边界条件必须想清楚。字符串长度为奇数，直接 false；全是左括号，最后 st 不为空，false；右括号先出现，st 为空，false；“([)]”这种交叉括号，栈顶是 ]，遇到 ) 不匹配，false。很多人做错不是因为不会栈，而是没把空栈和匹配失败的情况覆盖完整。

3.2 删除字符串中的所有相邻重复项

LeetCode 1047 本质上也是栈的应用，但你甚至不需要显式声明一个 stack，直接用 string 当栈：

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

这个思路是：维护一个“结果栈”，每次读入一个字符，如果它和栈顶相同，说明两个相邻重复了，弹掉栈顶；否则入栈。这就像小时候玩的消除游戏，只不过我们只消除相邻的重复项。

为什么不用真正的 stack ？因为 stack 没有反向遍历的能力，最后还要把元素倒出来再 reverse，麻烦。用 string 当栈，既保留栈的操作语义，又天然支持 back、push_back、pop_back，最后直接返回 res 就行。这种方法在后续“栈与队列”相关的字符串题里非常实用。

3.3 逆波兰表达式求值：操作数顺序是最大的坑

LeetCode 150 是栈应用里稍微复杂一点的题。逆波兰表达式也叫后缀表达式，运算符在操作数后面，计算机可以直接用栈求值，不需要处理括号和优先级。

int evalRPN(vector<string>& tokens) { stack<long long> st; for (string& s : tokens) { if (s == "+" || s == "-" || s == "*" || s == "/") { long long b = st.top(); st.pop(); long long a = st.top(); st.pop(); if (s == "+") st.push(a + b); else if (s == "-") st.push(a - b); else if (s == "*") st.push(a * b); else st.push(a / b); } else { st.push(stoll(s)); } } return st.top(); }

这里最容易犯的错误是减法和除法的操作数顺序。因为栈是后进先出，第一次 pop 出来的是右操作数，第二次 pop 出来的才是左操作数。例如表达式 “a b -”，栈中先入 a，再入 b，遇到 - 时先弹出 b，后弹出 a，所以应该计算 a - b，不能写成 b - a。

我见过太多学员在这里栽跟头：表达式是 “10 6 -”，结果算出 -4。排错时一查代码，发现写成了先弹出的数减去后弹出的数。为了避开这个坑，我会让学生先写注释：// 先弹出的是右操作数，后弹出的是左操作数，然后再写运算逻辑。

另外要注意字符串转数字。tokens 里既有正数也有负数，比如 “-11”，用 stoll 或 stoi 都行。LeetCode 的测试数据可能很大，我用 long long 做中间计算，避免乘法溢出。虽然本题答案范围在 int 内，但竞赛和工程里养成用更宽类型的习惯没坏处。

3.4 后续衔接：单调栈和表达式求值

Day10 的 part01 讲到这里，其实已经触碰到了两个更高阶的方向：单调栈和基于栈的表达式求值。

单调栈解决的是“找下一个更大/更小元素”这类问题。比如每日温度、接雨水、柱状图中最大的矩形。它的核心仍然是维护一个栈，但多了一个规则：入栈时把破坏单调性的元素弹出。这个规则本质上就是“什么时候弹出”的进阶版。

表达式求值则是逆波兰表达式的反向问题：给你中缀表达式如 “3 + 4 * 2”，怎么转成后缀，或者直接用两个栈（操作数栈和运算符栈）求值。这需要处理运算符优先级和括号，复杂度明显上了一个台阶。训练营一般放到后面的“字符串和模拟”专题，但 Day10 至少让你意识到：栈不只是用来匹配括号的，它是“编译器处理表达式”的基础结构。

4. 我在训练营里看到最多的几个错误

每次带 Day10，我都会总结一批出现频率极高的错误。这些错误不是“不会写代码”，而是对栈和队列操作边界的理解不够细。下面按高频程度列出来，每个都可以直接对照自己的代码检查。

4.1 栈空判断：先访问 top，再检查 empty

这是最典型的顺序错误。很多学员写括号匹配时，会写成：

if (st.top() == c && !st.empty()) { st.pop(); }

如果此时栈是空的，st.top() 已经触发了未定义行为，后面的 !st.empty() 根本来不及救你。正确的顺序应该是先检查 empty，再访问 top：

if (!st.empty() && st.top() == c) { st.pop(); }

这一点在 C++ 里尤其重要，因为 stack 的 top 在空栈时不会返回安全值，而是 UB。测试用例一多，可能一会儿崩、一会儿不崩，特别难排查。我的习惯是写任何访问 top 的代码前，先问自己：如果现在栈空，会发生什么？然后顺手补上判断。

4.2 数组模拟栈时 top 的语义混乱

训练营里不少学员平时用 std::stack 用惯了，突然手写数组，会把 top 初始化为 0，push 时却写成 stk[top] = x，然后 top++，等下次 push 就把上次的值覆盖了；或者 pop 时写了 stk[top--] = 0，把 top 减到负数。

这种问题没有捷径，只能靠统一约定。我建议所有手写栈一律使用“top 指向下一个写入位置”的语义，push 写 stk[top++] = x，pop 写 top--，peek 写 stk[top-1]。每写一道题前，先把 push/pop/empty/peek 四个函数抄一遍，或者直接在草稿纸上写死，就不会混。

4.3 逆波兰表达式里把减法和除法的顺序写反

前面已经详细说过，这里再强调一次。先弹出的 b 是右操作数，后弹出的 a 是左操作数，所以 a - b、a / b。很多人的记忆口诀是“出栈顺序和表达式顺序相反”，但真正写代码时还是容易顺手写成 b - a。

我提供一个自测方法：用最简单用例 “2 3 -” 跑一遍，期望结果是 -1。如果得到 1，说明顺序反了。所有涉及栈的题目，都应该先想清楚“第几次弹出的元素对应表达式的第几个操作数”。

4.4 混淆系统调用栈和算法数据结构栈

有学员问我：“C++ 里函数递归不是也用栈吗？那我手写栈模拟递归，会不会两个栈冲突，导致内存爆掉？”这是个好问题。

函数调用栈是操作系统和编译器维护的，每次函数调用都会压入一个栈帧，包含局部变量、返回地址等；递归层数太深，系统调用栈不够用，就会 stack overflow。而算法题里我们手写的栈，一般是一个全局数组或 vector，分配在静态区或堆上，和系统调用栈是两回事。

在做二叉树迭代遍历、模拟递归的时候，我们用“显式栈”替代“系统隐式栈”，目的是避免递归深度过大触发栈溢出。这个概念一定要分清，否则你会以为每一个 stack 变量的声明都在消耗系统调用栈，那理解就偏了。

4.5 队列的 front 和 back 语义混淆

用 std::queue 时，queue.front() 是队头，queue.back() 是队尾。用两个队列实现栈时，有人会把“主队列”和“备用队列”搞混，pop 时没有把前 n-1 个元素全部挪走，而是只挪了一部分，导致顺序错乱。

检查方法很简单：画三行图。第一行是初始队列，第二行是挪完前 n-1 个后的状态，第三行是弹出栈顶后的状态。只要图画对，代码基本不会错。

5. Day10 之后的衔接建议

栈和队列 part01 的内容量其实不大，但它是一个“分水岭”。前面学数组、链表时，你更多是在“处理数据”；从栈和队列开始，你开始“按规则处理数据”。这个思维转变，决定了后面二叉树、单调栈、图论能不能学顺畅。

5.1 做题顺序与时间分配

我建议 part01 当天至少完成五道题：用栈实现队列、用队列实现栈、有效的括号、删除字符串相邻重复项、逆波兰表达式求值。

前两道是结构题，重在理解互逆关系；后三道是应用题，重在理解“什么时候弹出”。如果时间有限，第二道用队列实现栈可以放到选做，因为它的思路和前两道有重叠，但不是必须。

做题时给自己一个硬性时间：每道题独立思考 20 分钟。20 分钟没有完整思路，就看题解。看完题解不是结束，而是盖住答案重新写一遍，写到自己能无报错通过为止。这个“闭卷重写”的步骤，比看十遍题解都管用。

5.2 复杂度和均摊分析的起点

Day10 第一次出现了“均摊 O(1)”这个概念。用两个栈实现队列里，每个元素最多被移动两次：一次进入 stIn，一次从 stIn 倒入 stOut。单次 pop 可能很慢，因为要搬一整个栈，但把连续多次操作看成一个整体，每次操作的平均代价就是 O(1)。

这个分析方法和后续动态数组扩容、哈希表 rehash、单调栈的总复杂度分析是一脉相承的。我建议从今天开始，每做完一题，都顺手写一行复杂度，而不是只在面试前临时记。复杂度不是背出来的，是在一遍遍手写分析中形成的直觉。

5.3 为单调栈、BFS、全栈项目准备什么

Day10 之后，栈会延伸出单调栈，用于解决“下一个更大元素”“接雨水”等问题；队列会延伸出 BFS，用于二叉树层序遍历、图的最短路径、拓扑排序。

在工程和全栈项目里，队列的概念同样无处不在。前端任务队列、后端消息队列、线程池的阻塞队列，本质上都是“生产者把任务放进队尾，消费者从队头取任务”。阻塞队列不过是在普通队列上加了容量限制和等待唤醒机制。如果你今天能把一个普通队列的手写实现搞清楚，后面接触 RabbitMQ、Redis 列表做消息队列、Kafka 的分区消费顺序时，会更容易抓到本质。

我在带训练营时发现一个规律：Day10 认真手写过代码、把两个“互相实现”的题真正跑通的人，到 Day20 学二叉树迭代遍历时，基本不需要回头补栈的知识；而跳过手写环节、只刷熟练度的人，经常在“用栈模拟中序遍历”的细节上卡住，再回来重新翻 Day10 的笔记。所以这一天的任务，看起来是五道题，其实是在帮你建立“数据结构操作规则”的肌肉记忆。

最后再分享一个带营多年的私藏技巧：学栈和队列时，不要只在 LeetCode 上做题，拿一张白纸，把“用两个栈实现队列”的完整状态转换画出来，包括空栈、满栈、倒腾、再入栈四个阶段。这张图一旦画明白，后面单调栈、表达式求值、甚至系统设计里的消息队列，你都会有一种“这题我见过”的踏实感。栈和队列不难，但值得你花这一天时间，认认真真把地基夯实。