栈和队列这一组题可以说是算法刷题路上最“亲民”的专题了。Day9我选了LC 232、LC 225、LC 20、LC 1047这四道两题是栈与队列的互实现两题是栈的经典应用场景。很多刚开始刷算法的人会忽略这个专题觉得“容器不是直接用就行了吗”但实际上这四道题能把“逻辑结构”和“底层存储”这两个概念彻底掰开揉碎——栈和队列的代码实现极其简单但背后涉及的操作约束、接口设计、复杂度摊还分析全是面试和竞赛里高频出现的考察点。这篇文章作为一个补档记录我会把这四道题的完整思路、手写代码、踩坑细节和延伸场景都写清楚。不论你是准备面试、打竞赛还是单纯想复健数据结构这份笔记都能直接拿来用。1. 为什么拿栈和队列开刀半天刷四道题的复健逻辑1.1 复健第一天的选题标准停刷算法大概半年之后重新捡起来我给自己定的规则很简单不求难、不求新先把最基础的数据结构重过一遍。数组、链表、栈、队列、哈希表、树这些是后续一切题型的“底座”。栈和队列看起来简单但很多人对它们的理解停留在“会用STL”的层面真让你手写一个模拟结构或者分析一段代码的复杂度反而容易卡住。我选这四道题的标准有三个题目短小精悍适合作为一天内的集中训练。前两题是“互相实现”能强迫你从行为层面理解两种结构而不只是背API。后两题是“栈的应用”能把栈的特性和真实场景括号匹配、相邻消除对应起来。复健阶段不要贪多一天一个专题、每个专题四道题节奏刚刚好。刷完之后你会发现后面做到二叉树遍历、单调栈、表达式求值这些题其实都在反复用到今天这四道题的思想。1.2 这四道题为什么要一起刷把这四道题放在一起不是说它们难度相当而是它们之间有一条完整的逻辑链你需要知道“栈”长什么样LIFO才能用栈去模拟队列FIFO。你需要知道“队列”长什么样FIFO才能用队列去模拟栈LIFO。你需要理解栈的“最近匹配”特性才能用它处理括号。你需要理解栈的“撤销回退”特性才能用它消除相邻重复项。这四条串起来你对栈和队列的理解就不是背概念了而是“在什么场景下这类结构天然能解决什么问题”。这个认知比会写几道题重要得多。1.3 刷前必补的最小知识栈和队列的底层差异在开始敲代码之前先明确两组核心差异后面对话都基于这两个点维度栈Stack队列Queue操作位置只允许在栈顶操作队尾入队队头出队出元素顺序LIFO后进先出FIFO先进先出核心操作push / pop / toppush入队 / pop出队 / front典型场景函数调用栈、括号匹配、表达式求值消息队列、BFS、打印机任务排队从C的角度看std::stack和std::queue都是容器适配器container adapter它们默认基于std::deque实现但你可以指定底层容器比如std::stackint, std::vectorint。这是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: stackint stackIn; stackint 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: queueint 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 复杂度对比单队列与双队列的取舍实现方式push 复杂度pop / top 复杂度空间复杂度双队列法O(1)O(n)O(n)单队列循环法O(n)O(1)O(n)两种方案都能通过题目测试选择哪一种取决于你希望哪边更快。如果业务场景里入栈操作远多于出栈双队列法更优如果出栈操作频繁单队列法更优。LeetCode题解里还有一种优化思路是用两个队列但不做搬移而是维护一个top变量直接记录栈顶只在pop时轮转能把top()降为O(1)。这里不展开了感兴趣可以自己推一下。3.3 一个容易被忽略的接口back()这题里面有一个细节特别容易被忽略std::queue除了front()之外还有back()方法可以直接访问队尾元素。这意味着在只需要“看一眼栈顶”的场景下你甚至可以不用轮转直接返回q.back()。为什么可以因为我们每次push之后都执行了轮转新元素永远在队头front()和back()指向同一个元素。但如果你的实现里没有轮转而是维护一个top变量back()的语义就会变——它始终指向最后入队的元素恰好就是栈顶。C的queue底层是dequeback()是O(1)所以直接用是完全可行的。4. LC 20 有效括号匹配栈不是唯一方案但栈是最好写的方案4.1 匹配问题的本质最近未匹配的左括号括号匹配是一道经典中的经典。核心逻辑一句话就能说清遇到左括号就入栈遇到右括号就检查栈顶是否是对应的左括号。如果不是或者栈为空直接返回false。遍历完整个字符串后栈必须为空。为什么这题非要用栈因为括号匹配的规则是“最近匹配”——[({})]是合法的[(])是非法的。数组能做到吗理论上可以你需要维护“当前还没匹配的左括号序列”并且始终只跟最后一个比较。这就是栈的定义所以栈是这个场景的天然选择。代码实现bool isValid(string s) { stackchar 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) { stackchar 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的复健记录就到这里。