算法训练营进行到 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 时 sizepop 时 size--判空 size 0判满 size N。留一个空位是竞赛常用写法初始化 head 0tail 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: stackint stIn; stackint 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没有 backdeque 才有所以别指望直接访问队尾。这两道题做完之后建议在草稿纸上画一下三个状态的转换初始空、连续 push、交替 push/pop。只要你能画清楚“数据从哪个容器流向哪个容器顺序发生了什么变化”这两题的底层逻辑就彻底掌握了。3. 三道经典栈应用题重点不是“用栈”而是“什么时候弹出”Day10 的 part01 里通常会配三四道栈的经典题。很多人的误区是题目一看“括号匹配”哦用栈再看“删除相邻重复项”哦还是用栈然后就开始套模板。但真正决定代码对错的是“什么时候入栈、什么时候出栈、栈空时怎么办”。3.1 有效的括号相邻匹配问题LeetCode 20 是栈的入门题。核心逻辑遍历字符串遇到左括号时入栈遇到右括号时检查栈顶是否匹配。常见的写法有两种一种是遇到左括号 push 左括号遇到右括号时比较栈顶另一种是遇到左括号时 push 对应的右括号遇到右括号时直接和栈顶比较。我更推荐第二种因为代码更短也不容易出现字符串比较的细节错误bool isValid(string s) { if (s.size() % 2 1) return false; stackchar 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(vectorstring tokens) { stacklong 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再访问 topif (!st.empty() st.top() c) { st.pop(); }这一点在 C 里尤其重要因为 stack 的 top 在空栈时不会返回安全值而是 UB。测试用例一多可能一会儿崩、一会儿不崩特别难排查。我的习惯是写任何访问 top 的代码前先问自己如果现在栈空会发生什么然后顺手补上判断。4.2 数组模拟栈时 top 的语义混乱训练营里不少学员平时用 std::stack 用惯了突然手写数组会把 top 初始化为 0push 时却写成 stk[top] x然后 top等下次 push 就把上次的值覆盖了或者 pop 时写了 stk[top--] 0把 top 减到负数。这种问题没有捷径只能靠统一约定。我建议所有手写栈一律使用“top 指向下一个写入位置”的语义push 写 stk[top] xpop 写 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 上做题拿一张白纸把“用两个栈实现队列”的完整状态转换画出来包括空栈、满栈、倒腾、再入栈四个阶段。这张图一旦画明白后面单调栈、表达式求值、甚至系统设计里的消息队列你都会有一种“这题我见过”的踏实感。栈和队列不难但值得你花这一天时间认认真真把地基夯实。