★ FEATURED ARTICLE 代码随想录训练营到第10天主题是栈和队列。如果你是从零开始刷的前面几天数组、链表、哈希表下来应该已经有一个感觉绝大多数题目本质上都是在和“存取方式”较劲。栈和队列最特别的地方在于它们底下其实还是数组或者链表但被强行规定了操作接口一个只能从一头进出一个只能一头进另一头出。这篇内容适合两类人一类是跟着训练营节奏走、想把这章题目吃透的新手另一类是刷过但总是混淆pop和peek、不清楚该用deque还是stack的老朋友。我会从底层原理讲到训练营第10天的四道核心题最后再聊一些刷题之外的工程联想。1. 为什么第10天要把栈和队列放在一起学先补上底层认知1.1 栈一条只能从一头进出的“死胡同”栈的抽象定义大家都会背后进先出LIFO。但真正动手写过实现的人可能反而比背定义的人印象更深。用数组实现一个栈只需要一个指针push写进数组当前位置并把指针往上移pop把指针往下移就行整个操作的时间复杂度是O(1)。用链表实现栈同样简单只在头部插入和删除即可。之所以它能做到O(1)就是因为操作被限制在了一个端点上。可能有人会问既然数组和链表都能实现栈那刷题时到底用什么这取决于语言。C里std::stack默认底层是deque也可以用vector或者list作为底层的模板参数Java里Stack是Vector的遗留子类官方其实更推荐使用ArrayDequePython没有专门叫Stack的类list自带append和pop天然就是栈。这些底层差异平时刷题不太容易暴露但当你真正做工程时就会开始关心内存分布、扩容成本和缓存命中率那时候回头再看栈的底层思路会完全不一样。栈在生活中最形象的类比就是死胡同最先进去的车要等后面的车全部倒出来之后才能出来换到编程场景函数调用的过程就是靠栈来管理的每一个函数调用都会在栈上分配一个“栈帧”记录局部变量、返回地址函数返回时栈帧被销毁。所以我在第10天上课前都会强烈建议先别着急刷题花20分钟把栈的数组实现和链表实现各写一遍你会发现后面所有栈题都能落到这两个模型上。1.2 队列两个口各管各的“排队窗口”队列的模型也很直白先进先出FIFO像食堂打饭排队先到的人先打到饭。实现上它比栈稍微绕一点。用数组实现队列如果每次出队都把后面的元素往前挪那出队就是O(n)这不可接受所以常规做法是循环队列维护队头和队尾两个指针指针走到数组尾部就回绕到0用浪费一个空间的方式区分队空和队满。用链表实现就省心很多队尾入队、队头出队两个指针分别维护前后即可。为什么要纠结这些细节因为代码随想录训练营后面很多题目尤其是一些模拟题会要求你“自己设计数据结构”或者“用现有容器模拟另一种容器”比如本题的232和225。你如果不知道栈和队列各自的实现代价就不会理解为什么“用栈实现队列”需要用两个栈而“用队列实现栈”只需要一个队列。底层的实现方式决定了上层操作的代价这两题就是逼你去体会这件事。2. 第10天核心题实操232用栈实现队列、225用队列实现栈2.1 232题解两个栈是怎么“接力”出队顺序的232的要求是只使用栈这个后进先出结构模拟出队列的先进先出效果。我第一眼看到这题的想法很简单栈是反的那用两个栈各反一次不就正过来了吗。这个直觉是对的但具体到代码有一些细节值得展开。维护两个栈一个叫stack_in只负责入队另一个叫stack_out只负责出队。push的时候直接往stack_in里压这点无脑做就行。难点在pop如果stack_out非空直接从stack_out弹出栈顶如果stack_out为空就把stack_in里的元素全部弹出来并按顺序压进stack_out。这一步相当于把进来的顺序倒了一次再从stack_out弹出时就变成了最先进来的元素。这里有一个均摊复杂度的概念值得多说一句。如果100个元素入队前99个都直接push最后一次pop才触发一次性搬运看起来最坏一次pop是O(n)但平均下来每个元素最多被搬进stack_in一次、搬进stack_out一次、弹出一次总共算下来还是O(1)的均摊复杂度。这个“均摊O(1)”在很多面试里会追问建议你自己画一个入队、出队交替进行的例子体会一下为什么不能只看单次操作。peek的实现我见过不少人的写法是直接看stack_out的栈顶不行的话再看stack_in的底部。这样逻辑上也能对但代码分支很多容易漏情况。我更推荐复用pop拿到结果之后再塞回stack_outclass MyQueue: def __init__(self): self.stack_in [] self.stack_out [] def push(self, x: int) - None: self.stack_in.append(x) def pop(self) - int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) - int: res self.pop() self.stack_out.append(res) return res def empty(self) - bool: return not self.stack_in and not self.stack_outpeek复用pop是很多参考答案的写法它牺牲了一次多出来的append和pop换来了逻辑的统一我建议新手先按这种方式写理解了之后再去优化分支判断。2.2 225题解一个队列也能实现栈关键在“转圈”用队列实现栈看起来是和232正好反过来但解法比232更反直觉其实只需要一个队列。核心思路是制造一些“无效操作”把顺序扭过来。如果用两个队列操作方式是这样的push时先放入queue2再把queue1里的元素全部倒入queue2然后交换queue1和queue2的名字。这样queue1里的元素始终保持“最后入队的在前面”。如果用一个队列做法更简单每次push之后把队列里前面的n-1个元素依次出队再重新入队这样最后一个入队的元素就绕到了队头也就是“栈顶”。我放一个单队列版本的Python代码from collections import deque class MyStack: def __init__(self): self.queue deque() def push(self, x: int) - None: self.queue.append(x) for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) def pop(self) - int: return self.queue.popleft() def top(self) - int: return self.queue[0] def empty(self) - bool: return not self.queue这个实现里push的成本是O(n)因为每入队一个元素都要把前面所有元素往后挪一个位置。有人可能会想能不能让pop变成O(n)、push保持O(1)当然可以那就是在pop的时候把除了队尾元素之外的元素全部搬到另一个队列里。两种方案各有取舍刷题时我建议你各写一遍感受一下“操作发生在入口还是出口”对复杂度分布的影响。2.3 容器选择deque还是listStack还是ArrayDeque写代码时语言选择也很影响手感。Python里很多人习惯用list当栈append和pop都是O(1)没问题但当队列用就会出问题因为list的pop(0)是O(n)。所以队列一定要用collections.deque它的popleft才是O(1)。C里std::queue默认底层是dequestd::stack默认也是deque如果你只是刷题直接用std::stack和std::queue就行Java则推荐用LinkedList实现队列、ArrayDeque实现栈不要去用Stack类。这里插入一个工程上的联想很多框架里的“线程池阻塞队列”就是队列模型生产者和消费者之间靠一个队列解耦而你写的每一个递归函数背后都是函数栈帧的创建与销毁。刷题时学到的“进出顺序”约束到了工程里就是消息队列的顺序保证、调用栈的回溯路径抽象模型一模一样。不过第10天阶段先别贪多抓住两种模型的操作特性就好。3. 栈怎么处理配对问题20有效的括号与1047删除相邻重复项3.1 20题解括号匹配就是“最近的左括号必须对应最近的右括号”有效的括号这题本质上考察的是遇见一个右括号时它要和“最近的未匹配左括号”配对。这个“最近”两个字天然就是栈的适用场景。维护一个栈遇到左括号就压栈遇到右括号就弹出栈顶并检查是不是匹配的类型不匹配或者栈为空就返回false。我在训练营里见过不少同学一上来就写四五个if判断左括号和右括号的计数这种思路在只有一种括号时还行有三种括号时就会出错因为“数量对得上”不代表“位置对得上”。用栈的话三种括号统一处理起来非常干净class Solution: def isValid(self, s: str) - bool: if len(s) % 2 1: return False stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping: if not stack or stack[-1] ! mapping[ch]: return False stack.pop() else: stack.append(ch) return not stack这里有两个细节值得记一下。第一个是提前剪枝字符串长度如果是奇数直接返回False不用再做任何入栈操作第二个是mapping的写法用右括号当key遇到右括号时去查它应该配对的左括号比用左括号当key分支更少。我看过很多代码在遇到右括号时用elif判断三种情况那样可读性和性能都不如一个字典来的干净。3.2 1047题解把栈当作“临时缓冲区”来消除相邻重复1047和20共用同一个核心思想当前字符和栈顶相等就说明出现了相邻重复栈顶弹出不相等就把当前字符压入。最后栈里剩下的字符按顺序拼接就是答案。代码非常短class Solution: def removeDuplicates(self, s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)这里有一个很容易被忽略的坑返回结果时栈底的元素应该是结果字符串的前缀所以直接join栈的内容就行不需要反转。有些习惯从栈顶往外拼的人会不小心写成先拼栈顶再反转反而多此一举。这两道题放在第10天我觉得最大的价值不是学会这两道题本身而是建立起“栈能处理相邻相关性问题”的直觉。你可能想不到后续很多看似高阶的题目比如单调栈里的接雨水、柱状图中最大的矩形底层的操作逻辑都还是“遇到破坏单调性的元素就从栈里弹出一些元素并计算结果”。所以说第10天这几道题真的很像母题值得亲手实现不止一遍。3.3 配对与消除题的常见翻车点这一章我最常看到的问题有三个。第一个是20题里忘了检查栈是否为空例如输入“())”处理完两个括号后栈是空的最后的return不写not stack就会直接漏掉“左括号冗余”这一种情况。第二个是1047题返回结果时反转方向搞错前面说了直接用join即可不要额外反转。第三个是忽略字符串长度的奇偶剪枝这个虽然不影响正确性但在循环里多做很多没意义的入栈操作养成先做边界判断的习惯没坏处。我自己的建议是这两道题写完以后用最暴力的方式各测十组用例包括空字符串、全重复、左右交替重复、只含一种括号等情况比只提交一次通过更有价值。测试的过程就是在帮你把栈的操作顺序内化成直觉。4. 从训练营第10天向外看栈和队列的工程投影4.1 逆波兰表达式150题里的操作数顺序陷阱严格来说150逆波兰表达式求值有的版本会放在第10天前后它也是栈的经典应用。逆波兰表达式的意思是运算符跟在两个操作数后面计算时遇到数字就压栈遇到运算符就弹出两个数字计算完再压回去。代码逻辑非常短但有一个非常隐蔽的坑弹栈时先出来的是右操作数后出来的是左操作数。举个例子表达式“3 - 4”写成逆波兰是“3 4 -”先弹出4再弹出3如果写作a b或者a - b时把顺序搞反减法会得到1而不是-1除法也会得到完全不同的结果。另一个坑是Python的整除如果两个数一正一负比如-3除以2期望的数学结果是-1.5取整后一般是-1但如果用a // b在Python里结果是-2因为它向下取整。正确写法是int(a / b)这是我在实际提交里踩过最多次的坑建议你直接背下来。4.2 单调栈和单调队列今天种下的种子代码随想录训练营的题目单里栈和队列这一章的后半部分通常会提到239滑动窗口最大值和347前K个高频元素其中239就是单调队列而很多读者可能听说过“单调栈揭秘”这个词。单调栈简单说就是让栈内元素保持单调递增或者单调递减。当新元素破坏单调性时把不满足条件的栈顶元素弹出并结算常用于找数组中每个元素左右两边第一个比它大或比它小的位置。为什么要在第10天里提前提一句因为很多同学刷到后面接雨水时不清楚为什么要用栈其实从1047的经验就能顺过来栈天然适合处理“相邻元素之间的先后/大小关系”而单调栈是在这个基础上增加了“淘汰劣质候选”的规则。今天这几道题让你先熟悉栈顶操作后面理解单调栈时会省很多力。4.3 从算法题到工程阻塞队列、消息队列与幂等消费栈和队列不只是算法题里的主角也是工程里重复出现的抽象。队列在生产者和消费者之间搭桥就是消息队列的本质线程池的阻塞队列选择本质上是问“当队列满的时候任务请求该被阻塞还是拒绝”这是对队列容量和吞吐量的权衡。再比如消息队列重复消费问题消费者收到两条相同的消息要去重保证幂等性这既和队列的顺序语义有关也和我们今天在1047里用“当前状态对照历史状态”的思路相通。我不是说刷完第10天就能解决这些工程难题而是想说当你把栈和队列的进出顺序、底层实现、复杂度分布搞明白以后再看这些框架源码时会觉得很多设计并不是天马行空。先把理论基础和代码基本功打牢模块模型自然会长出来。5. 实操心得与问题排查给刷完第10天的你一份速查清单5.1 常见错误速查表症状根因解决思路用栈实现队列时pop返回空stack_out为空时直接弹出先判断stack_out为空才倒灌stack_in用队列实现栈时top拿到的是队尾没有在push后调整队列顺序push后把前n-1个元素移到队尾括号匹配对“())”返回正确没检查最后栈是否为空返回not stack而不是True1047返回字符串顺序错从栈顶拼接后又反转直接“”.join(stack)即可Python负数除法结果不对用了a // b而不是int(a / b)除法统一用int(a / b)list当队列用超时list.pop(0)是O(n)改用collections.deque这张表里的每一个场景我都实际遇到过。尤其是最后一条我刚开始用Python刷题时一直用list当队列结果在滑动窗口这类需要频繁出队的题目里频繁超时换成deque之后一下就过了。语言内置容器的底层特性在刷题初期就该形成条件反射。5.2 刷题顺序建议与时间分配第10天如果按训练营的正常节奏我建议把时间这样分配先花20分钟自己画图理解栈和队列的数组/链表实现再花40分钟左右做232和225两题做完之后紧接着做20和1047最后留20分钟把四道题复盘一遍总结成自己的模板。很多人容易贪快四道题写完就急着赶进度其实栈和队列这一章的模板复用性很高今天总结的比较、入栈、出栈、边界判断后面单调栈、字符串匹配、表达式解析都能直接套。复盘的时候我习惯用表格记录每一题的三个信息核心思路一句话、时间复杂度、我踩的坑。等刷完整个训练营回头翻会发现很多坑是反复出现的比如边界检查、顺序颠倒、队列容器的选择。5.3 一些掏心窝的建议最后说几句个人体会。栈和队列看着简单但它可能是整份算法提纲里最容易被“显得会”的一章因为它代码短、思路直白。但代码短不代表理解浅。我遇到很多人能把232的代码背下来但你问他为什么需要两个栈他会说“一个正序一个倒序”再问他时间复杂度为什么均摊O(1)他就支支吾吾了。这其实是训练营最想让你突破的地方不只是把题做出来而是把每一步操作的本质说出来。我自己在第10天的经验是一定要在纸上手动模拟整段入队出队过程。拿232来说你把数组1、2、3、4按顺序入栈A再倒到栈B弹出的顺序是不是正好是1、2、3、4这个过程用笔画一遍比看十遍代码都有用。等你把这一层想通了第10天的四道题也就是同一个道理换着花样考你而已。刷到这里的你应该已经把第10天的核心题过了一遍。如果你还觉得有些地方没吃透我的建议是先别急着刷下一章拿一个具体的操作序列比如“入队1、2、3出队一个入队4再出队两个”在纸上模拟一遍双栈队列的完整变化你会瞬间明白为什么需要第二个栈。栈和队列的妙处在于它把“顺序”变成了可以被操纵的规则弄懂这个之后无论是栈帧的创建与销毁还是消息队列里那些晦涩的工程问题你会觉得它们隐隐约约都指向同一种东西。按照自己的节奏把这四道题吃透后面还有更多有意思的题等你。
阅读完成 · 觉得有帮助？
