刷代码随想录算法训练营刷到 Day09栈与队列 part01我最大的感受是题量不大但每一道都在逼你从“会用API”切换到“理解结构”。这一天的内容在代码随想录整个算法路线里属于承上启下的一站——前面刚把数组、链表、哈希表这些基础结构过完从这一天开始你接触的不再是单个值的存取而是“操作受限条件下的模拟”。栈和队列概念上三分钟就能背下来可真到用栈实现队列、用队列实现栈的时候不少人直接就懵了。这篇文章写给正在跟代码随想录训练营的同学也写给准备面试却总在基础数据结构上翻车的人。我会把 Day09 涉及的核心题目拆开揉碎说清楚每道题在考什么、实现时有哪些容易漏的细节、以及栈和队列在工程里到底以什么形态出现。很多内容是我实际手写代码、带新人复盘时反复踩过的坑希望对你有用。1. 训练营Day09“看起来简单”但要理解到位的一课1.1 为什么栈和队列要专门花掉一整天如果你只看代码随想录的目录可能会觉得奇怪栈和队列不就是两个线性结构吗后进先出、先进先出各背一个概念做几道题就完了为什么要单独占一天我的理解是栈和队列在刷题体系里的定位根本不是“两个数据结构”而是一组思维工具。很多更复杂的题目比如表达式求值、单调栈、单调队列优化DP、二叉树的层序遍历底层都会落到“这里是不是应该用一个栈”“那里是不是应该用一个队列”。Day09 做的工作就是提前把这些工具的适用场景打磨好。代码随想录把栈与队列拆成了 part01 和 part02 两个阶段。Day09 的 part01 主要解决四件事明确栈和队列的本质操作约束学会用两个栈去模拟队列学会用两个队列甚至一个队列去模拟栈处理两个经典的“匹配消除”类问题——有效括号和字符串相邻重复项。你可以把这一天理解为“结构互转与匹配消除”专项训练。它不考你对 API 的背诵而是考你有没有弄清“为什么栈能实现队列、为什么队列也能实现栈”背后的顺序控制逻辑。1.2 这一天的核心题目在考同一个共性LeetCode 232用栈实现队列、225用队列实现栈、20有效的括号、1047删除字符串中的所有相邻重复项这四道题如果只是按题号刷很容易刷完就忘。但你把这四道题放在一起看会发现它们其实都在回答一个问题当一个操作只被允许在特定端点发生时数据顺序会发生什么变化栈只允许在栈顶操作所以它的天然能力是“反转顺序”——你把 1、2、3 依次入栈出栈顺序就是 3、2、1。队列只允许在队尾入、队头出所以它的天然能力是“维持顺序”——你把 1、2、3 依次入队出队顺序还是 1、2、3。用栈模拟队列本质是在用“两个反转”抵消反转得到正序。用队列模拟栈本质是在用“有限度的重排”让最后进来的元素先出去。括号匹配和相邻重复项删除则是利用栈的“只关心最新状态”特性把匹配问题化简成 O(n) 的一次扫描。这个共性想清楚之后Day09 的代码细节就不难记了。2. 先搞懂两件事栈解决什么问题队列解决什么问题2.1 一个叠盘子的比喻讲清LIFO和FIFO栈的教科书定义是后进先出Last In First OutLIFO。听起来抽象你可以想一个弹簧式碗碟架你放上去的最后一个盘子一定是你最先拿走的那一个。你不想为了拿最下面那个盘子去把上面的全挪走所以日常使用里你只会碰最顶上的那个。队列的教科书定义是先进先出First In First OutFIFO。这个更好理解就是食堂打饭的队伍先排队的人先打到饭后来的人排后面。打饭阿姨只服务队头新来的同学只能站队尾。这两句话看起来简单但你要进一步追问一个问题为什么这两个结构这么设计答案是“限制”。数组和链表给了你随心所欲访问任意位置的能力但很多场景里你根本不需要那种自由。比如浏览器的后退按钮你只需要“最近访问的那个页面先回来”而不是“按任意页面顺序跳”。操作系统里的打印机任务调度你只需要“谁先提交谁先打印”而不是插队。当访问模式非常明确时把自由度去掉、只保留两个端点的操作反而让实现更简单、性能更可控。栈和队列都是线性结构的收紧版它们内部依然是顺序存储或链式存储但对外暴露的接口被限制在了“栈顶”和“队头队尾”。2.2 工程场景里边谁是栈谁是队列我辅导过的不少新人在 LeetCode 上能熟练地用栈解决括号匹配但一进业务代码就想不到它们了。这里我列一个工程对照表帮助你把抽象结构和真实世界对应起来结构核心能力典型工程场景栈临时保存中间状态逆序恢复函数调用栈、文本编辑器撤销、浏览器后退、表达式求值、深度优先搜索队列按到达顺序缓冲公平处理打印机任务、线程池任务队列、消息队列、广度优先搜索、请求限流削峰这里多说一句很多人一听“队列”就想到 Kafka、RabbitMQ、RocketMQ 这类消息队列中间件。它们的核心模型确实是先进先出的队列但中间件里还包含了生产者消费者模型、重复消费处理、顺序保证、消息持久化等一堆东西。底层那个基本队列思想就是 Day09 里你现在刷的这个队列。这也是为什么很多大厂面试官喜欢从一个简单的“队列模拟栈”问题出发一路追问到阻塞队列怎么实现、线程池里该选哪种队列——基础结构没吃透后面根本答不上去。3. 用栈实现队列232题两个栈倒来倒去的正确姿势3.1 输入栈和输出栈的分工逻辑LeetCode 232 的要求是只能使用两个栈实现队列的 push、pop、peek、empty 操作。注意你只能访问栈顶但你希望模拟出来的队列具备“先入先出”的特征。解法是引入两个栈一个叫stackIn专门负责入队一个叫stackOut专门负责出队。push(x)直接把元素压入stackInpop()如果stackOut为空就把stackIn的所有元素依次弹出并压入stackOut然后从stackOut弹出栈顶peek()复用pop()的逻辑拿到队头再把队头元素压回去empty()两个栈都为空时队列才为空。核心逻辑用文字走一遍先push(1)、push(2)、push(3)此时stackIn从底到顶是 [1, 2, 3]调用pop()把stackIn全部弹出再压入stackOut于是stackOut从底到顶是 [3, 2, 1]然后弹出stackOut的栈顶得到 1。你看1 最早进来也最早出去队列的样子就出来了。这里最关键的一句话只有在stackOut为空的时候才需要把stackIn的数据倒过来。这个点很多人会写错下面单独展开。3.2 倒数据只有一种时机写错就变死循环我第一次做这道题的时候把倒数据的逻辑写成了“每次 pop 前都把 stackIn 全部倒入 stackOut”结果第二次 pop 就全乱了。为什么会乱因为队列的顺序是连续的。假设我push(1)、push(2)pop()一次得到 1再push(3)此时stackOut里还剩 [2]stackIn里是 [3]。如果你按“每次 pop 前都倒”就会再把 [3] 倒进stackOut它变成 [2, 3]然后弹出 2看起来好像碰巧对但如果连续操作几次顺序就会被打乱。正确的做法是stackOut非空时直接弹出stackOut的栈顶即可因为栈顶就是当前队头。只有当stackOut空了你才执行一次“倾倒”操作把stackIn里现在所有的元素整体搬运过去。用 C 写一个参考实现class MyQueue { private: stackint stackIn; stackint stackOut; void transfer() { // 只有 stackOut 为空时才倒数据否则会打乱已有顺序 if (stackOut.empty()) { while (!stackIn.empty()) { stackOut.push(stackIn.top()); stackIn.pop(); } } } public: void push(int x) { stackIn.push(x); } int pop() { transfer(); int val stackOut.top(); stackOut.pop(); return val; } int peek() { transfer(); return stackOut.top(); } bool empty() { return stackIn.empty() stackOut.empty(); } };很多题解里peek是这样写的先调用一次pop()拿到栈顶元素再把它 push 回stackOut。这种写法本身没问题但注意pop()里已经调用了transfer()所以peek里不要再重复调用一次搬运逻辑否则会造成栈的顺序错乱。3.3 均摊复杂度的直觉这道题经常被追问你每次都“一次搬运 N 个元素”那 pop 不就成了 O(n) 吗为什么大家都说这是 O(1) 均摊原因是搬运不是每次 pop 都发生。你搬一次 N 个元素之后如果连续 pop N 次每一次都直接从stackOut拿总共只需要 O(N) 的时间平摊到 N 次 pop 上每次是 O(1)。这就是经典的分摊分析。你可以把“搬运”想象成你一次性从仓库把一箱货搬到柜台之后一段时间内拿货都不用再跑仓库。另外还有一个工程细节pop和peek如果遇到空队列应该抛异常还是返回特殊值LeetCode 的测试用例保证了不会对空队列调用这两个操作但真实代码里可不能这么乐观。我在封装这样的类时通常会在transfer()里检查stackIn是否也为空为空就声明runtime_error或者返回optionalint否则在业务代码里很容易踩到隐蔽的崩溃。4. 用队列实现栈225题一个队列也能模拟4.1 官方思路与常见的两队列版本232 用两个栈模拟队列很多人的第一反应是那 225 是不是用两个队列对称写就行了实际上队列模拟栈的套路和栈模拟队列完全不同。栈模拟队列靠的是“把倒序再倒序变回正序”而队列本身就是正序它不具备反转能力所以你必须主动“重排”。最常见的双队列版本是维护queue1作为主队列queue2作为辅助队列。push(x)时把 x 直接压入queue1pop()时把queue1中前 n-1 个元素全部出队并入queue2然后弹出queue1剩下的那个队头这就是栈顶弹出后交换queue1和queue2保证主队列里存的始终是当前元素。这个版本很好理解但它多用了辅助队列而且每次 pop 都要倒腾所有元素。其实队列模拟栈有一个更精简的思路只用单个队列靠“转圈”实现。4.2 核心操作让队尾元素变成队头单队列版本的核心操作一句话就能说清每次 push 之后把队列前面的元素全部重新入队让新元素变成队头。比如队列现在从队头到队尾是 [1, 2, 3]我想模拟栈的 push(4) 操作。先把 4 入队变成 [1, 2, 3, 4]然后循环 size-1 次每次把队头出队再重新入队依次弹出 1、2、3 再放到队尾。最终队列变成 [4, 1, 2, 3]队头是 4完美模拟了“最后入栈的在栈顶”。pop 就更简单直接出队队头即可因为队头就是栈顶。用 C 实现class MyStack { private: queueint q; public: void push(int x) { q.push(x); int n q.size(); // 把前 n-1 个元素移到队尾让 x 跑到队头 for (int i 0; i n - 1; i) { q.push(q.front()); q.pop(); } } int pop() { int val q.front(); q.pop(); return val; } int peek() { return q.front(); } bool empty() { return q.empty(); } };注意这里的n必须在入队之后重新取q.size()不能用之前记录的 size否则你可能会把刚入队的x也当成旧元素移走导致顺序错误。这个小细节我见过至少三个人踩过。你可以把“push 后转圈”当成这类代码的固定动作先入队再数一遍个数最后转 len-1 次。4.3 两种实现的时间复杂度假象单队列和双队列版本在时间复杂度上其实没有本质差别每次 push 都是 O(n)pop 是 O(1)。相比之下双队列版本每次 pop 要把 n-1 个元素搬去辅助队列再搬回来也是 O(n)。所以两个版本各有取舍单队列省空间双队列思路更容易向面试官解释。另外提一个进阶点如果你想用两个队列做到 push O(1)、pop O(n)可以把“新元素直接入队pop 时循环调整”而不是在 push 时调整。两种做法逻辑等价只是把重排的时机从入队挪到了出队。面试问性能时就答栈模拟队列的难点在于让先进来的先出去队列模拟栈的难点在于让最后进来的先出去二者必然有一个操作是 O(n) 的因为队列本身不具备逆序能力。能把这句话说出来面试官基本就知道你是真懂了。5. 有效括号20题括号匹配的“压栈消消乐”5.1 三种失败场景一样都不能漏LeetCode 20 是栈应用里最经典的入门题。给定一个只包含( ) { } [ ]的字符串判断括号是否有效。有效需要满足左括号必须用相同类型右括号闭合且按正确顺序闭合。用栈做这个题的直觉来自现实中的括号结构([{}])合法()[]{}合法但(]、([)]、(()都不合法。为什么因为括号天生是“嵌套的”而栈天然擅长处理嵌套结构——你只需要维护“最近一个未闭合的左括号”。核心逻辑扫描字符串遇到左括号就把对应的右括号压栈遇到右括号时如果栈顶正好是它就弹出否则直接判定不合法。扫描结束后栈必须为空说明所有左括号都被闭合了。这个题有三种失败情况缺一不可左括号比右括号多比如(()扫描结束栈里还有元素右括号比左括号多比如())扫描中途栈已经空了却来了右括号左右括号数量一致但类型不匹配比如(]栈顶和当前右括号对不上。很多初学代码随想录的学员只想着“数量相等就合法”写出来的版本不能处理([)]这类嵌套错误。实际上栈解法天然解决了它([)]扫描到]时栈顶是(不匹配直接返回 false。5.2 压右括号的小技巧与代码实现这里分享一个代码层面的小技巧压栈时不压左括号而是压与之匹配的右括号。这样在判断时就不用写一堆映射关系直接比对字符是否相等即可。class Solution { public: bool isValid(string s) { stackchar st; for (char c : s) { if (c () st.push()); else if (c [) st.push(]); else if (c {) st.push(}); else { // 右括号来了如果栈空说明左括号不够直接 false if (st.empty() || st.top() ! c) return false; st.pop(); } } // 栈空才说明所有左括号都被正确闭合 return st.empty(); } };这个实现的巧妙之处在于当遇到右括号时你只需要检查两件事栈是不是空、栈顶和当前字符等不等。栈空说明右括号多了不等说明类型不匹配。省去了从 char 到 char 的映射函数代码也更不容易出错。我在带新人时发现一个常见的低级错误有人会把左括号也压栈然后用一个unordered_mapchar, char来查配对结果忘了处理map.find失败的情况。不是不能写但 LeetCode 上最简单的测试用例确实用“压右括号”更短更稳。6. 删除相邻重复项1047题栈把字符串“原地净化”6.1 从O(n²)到O(n)的思路转变LeetCode 1047 的题目描述是给出由小写字母组成的字符串重复项删除操作会选择两个相邻且相同的字母并删除它们。反复执行这个操作直到无法继续删除。比如abbaca先删除中间的bb得到aaca再删除aa最后返回ca。如果你第一次看到这个题可能会想这不是简单题吗每次都扫描字符串找到一对相邻相同字符就删掉然后从头再扫直到没有相邻相同字符为止。这样写确实能过测试用例但时间复杂度是 O(n²)字符串一长就超时。栈解法把问题变成了一个单次扫描问题初始化一个空栈遍历字符串的每个字符 c如果栈不为空且栈顶等于 c说明 c 和上一个字符是一对相邻重复项弹出栈顶否则把 c 压栈最后栈里剩的字符按从栈底到栈顶的顺序拼接起来就是答案。为什么栈能做到因为栈永远只关心“最后一个还没被处理的字符”。字符串从左往右扫一个字符能不能被删掉只取决于它和上一个保留下来的字符是否相同。这个“上一个保留字符”恰好就是栈顶。6.2 删除后的顺序与拼接反转问题用abbaca走一遍扫描 a压栈 [a]扫描 bb 不等于 a压栈 [a, b]扫描 b栈顶是 b弹出栈变成 [a]扫描 a栈顶是 a弹出栈变成空扫描 c压栈 [c]扫描 aa 不等于 c压栈 [c, a]。最后栈里是 [c, a]从底到顶拼接成ca正确。这里有一个几乎所有新手都会踩的坑栈的出栈顺序是反的。如果你直接把栈里所有元素弹出拼接得到的是ac不是ca。所以最后一定要做一次顺序处理。class Solution { public: string removeDuplicates(string s) { string st; for (char c : s) { if (!st.empty() st.back() c) { st.pop_back(); } else { st.push_back(c); } } return st; } };上面的实现直接用string当栈用连stackchar都省了。st.back()就是栈顶st.pop_back()就是出栈最后返回的st天然是从底到顶的正确顺序不需要反转。这个技巧在代码随想录的题解里也出现过实战里很常用面试时你可以主动提一下“用 string 代替 stack 可以避免最后的拼接反转”。6.3 变体删除连续三个相同字符时栈里要存点什么1047 的进阶变体是如果题目改成“删除连续三个相同字符”你的记录方式就要升级了。因为单纯的栈顶比较只能判断“相邻两个相同”判断不了“已经连续出现几个”。这时候你需要让栈节点变成pairchar, int保存字符和当前连续次数。每来一个新字符要么清空计数重新压栈要么累加计数当计数等于 3 时弹出。这个写法在“字符串压缩”“游戏消除”类题目里非常常见理解了它你再看单调栈一类题目时也会更容易理解“栈里存的不是普通节点而是带附加信息的节点”这种思维。7. 别把栈和队列当“容器”底层实现与工程选型7.1 STL里的栈和队列是容器适配器代码随想录在 Day09 里专门强调过一件事栈和队列在 C STL 中并不是底层容器而是容器适配器container adapter。这句话很多人第一遍看没感觉直到后来被面试官问到才意识到它的分量。什么叫适配器就是它本身不负责存储数据而是封装另一个容器把那个容器的接口改造成“只开放栈顶操作”或“只开放队头队尾操作”。STL 里stack和queue默认使用的底层容器都是deque双端队列但你也可以显式指定用vector或list作为底层存储。为什么默认选 deque 而不是 vector因为 deque 的头尾两端插入删除都是均摊 O(1)可以同时满足栈的尾端操作需求和队列的头尾两端操作需求。vector 的尾端操作很强但头部删除是 O(n)做队列不够格。list 两端操作也行但节点分散在内存各处缓存局部性不如 deque。可以说默认 deque 是一个非常合理的工程选择。// 示例显式指定底层容器 stackint, vectorint customStack; // 让栈用 vector 存储 queueint, listint customQueue; // 让队列用 list 存储如果你只是刷题写算法这些可能一辈子用不上但搞清楚这一点可以防止你把“栈”和“vector”的底层能力混为一谈。LeetCode 上有些“用队列实现栈”的题目如果你看到有的题解直接用了deque的push_front、pop_back就知道他们不是真正实现了栈而是绕过了限制——这种操作在刷题时无伤大雅但面试手写时最好按题目约束来。7.2 数据结构里的栈、内存里的栈区别搞混很多人在学这部分的时候容易产生一个困惑数据结构里的栈和计算机内存里的“栈区”call stack到底是不是同一个东西它们共享同一个思想后进先出。函数调用时后调用的函数后返回操作系统正是利用栈这个性质来管理函数调用现场。每个函数栈帧里保存返回地址、局部变量函数返回时栈帧被弹出控制权交还给上一个函数。所以你可以说“函数调用栈是栈这个数据结构在系统层面的一个实装”。但它们不是同一个层面的东西。数据结构里的栈是一个抽象逻辑结构你可以自己用数组实现、用链表实现。内存栈区则是一个具体的运行时内存布局由编译器生成代码和操作系统协作维护。更重要的是你在栈上创建的局部变量和你定义的一个std::stackint对象不是一回事。前者占用的是进程的调用栈内存后者可能内部用 deque 在堆上分配存储。理解这个区别对你排查栈溢出类问题也有帮助。如果你在刷代码随想录的递归专题时遇到栈溢出回想一下这里递归深度太大本质是函数调用栈被撑爆了跟你在数据结构课上学的“栈溢出”是同一个底层机制。7.3 工程里那些“披着中间件外衣”的队列既然热搜词里反复提到消息队列、阻塞队列、线程池阻塞队列选型我在这个章节还是想展开一下因为这些工程概念在 Day09 学完之后完全可以直接当成队列的应用实例来理解。Kafka一个大吞吐量的分布式消息流平台topic 内部按分区维护顺序每个分区就是一个先进先出的队列RabbitMQ注重路由和可靠投递队列是消费的基本单位支持确认机制RocketMQ阿里开源的消息队列布局上是“queue”模型重点解决海量消息堆积和高可用。它们之间选型差异很大比如 Kafka 牺牲一定的即时性换取吞吐RabbitMQ 在路由能力上更灵活RocketMQ 在事务消息、延迟消息上做得更顺手。但无论哪个中间件底层消费者拉取或者服务端投递的本质动作都包含一个队列在维持顺序。如果你能手写出基于deque加锁的线程安全阻塞队列再去看这些中间件的文档会发现很多术语突然就通了。我更想强调的是刷 Day09 时不要只盯着“如何用两个栈实现队列”这一道题。你可以顺手想一想线程池的work queue为什么现在主流推荐有界队列加拒绝策略消息消费者 group 里如果只有一个消费者消费顺序就是队列顺序如果多个消费者并发消费同一个主题分区顺序保证就需要额外机制了。这些问题的起点都是队列的先进先出这一条规则。8. Day09刷题复盘三个建议和四个误区8.1 三个建议第一个建议每道题写代码前先手画一次“入栈出栈顺序图”。我当初刷 232 和 225 的时候光看题解觉得懂了一写代码就错后来强迫自己在纸上把[1,2,3]的每一步操作画出来才真正理解了为什么stackOut空的时候才能倒数据。画图的成本很低但能避免你反复调试。第二个建议用“结构能力”而不是“题号”去记忆。栈的能力是逆序和匹配消除队列的能力是保序和缓冲。遇到一个新题先问自己这是需要“逆序恢复”还是“顺序处理”再考虑具体用什么结构。这个方法比疯狂刷题管用得多。第三个建议把 LeetCode 题和工程概念串起来。学完栈模拟队列就去搜一下阻塞队列怎么实现学完队列和 BFS就去看一下消息队列的顺序保证怎么做。算法题的输入样例往往抽象但你把它放到一个具体场景里理解深度完全不一样。8.2 四个常见误区误区一以为栈和队列是容器。它们是“受限的抽象结构”可以用数组、链表任何底层实现。这个误解会影响你后续学习优先队列、单调栈等进阶内容。误区二以为栈和队列只能互相模拟没有实际价值。恰恰相反它们在函数调用、表达式求值、文本编辑撤销、任务调度里无处不在。模拟题只是训练你的结构理解不代表它们只活在 LeetCode 里。误区三写 232 时反复倒数据。只要stackOut还有元素就不能倒倒了顺序就乱。这个错误本质上是没有理解“一次搬运多次使用”的分摊思想。误区四写 225 时不知道什么时候调整队列。有人会在 pop 时调整完下次 push 却忘了维护“新元素在队头”的约束导致 pop 得到旧元素。解决办法是把调整逻辑固定封装在一个方法里或者干脆在 push 之后立刻调整减少出错机会。我个人实际操作中的体会是栈与队列 part01 这一天最值得花时间的不是把四道题的代码背下来而是反复追问自己“为什么这题要用栈、用队列行不行、用数组行不行”。想通了这些问题后续遇到单调栈、单调队列、BFS 层序遍历这些内容时你会明显感觉到基础更牢不会每学一个新专题就推倒重来一次。