代码随想录刷到第十天栈和队列这个专题终于上场了。说实话我当年在学校上《数据结构》的时候栈和队列是分开两章讲的、分开考的当时觉得这就是两个毫无关系的小容器一个后进先出一个先进先出背熟定义就能应付考试。但真正按这套算法路线系统刷题之后我发现这俩东西远比我印象里重要——数组、链表、哈希表、字符串练的是“遍历”和“存储”的直觉而栈和队列恰恰是给这些直觉定性的关键一个管逆序回退一个管顺序排队。这篇我把代码随想录第十天的核心题目和这些年实际工程里的经验放在一起专门聊聊栈和队列到底该怎么学、怎么用顺便把几个特别容易混的概念——数据结构队列、阻塞队列、消息队列、调用栈——一次拆干净。如果你是正在刷代码随想录的读者这篇文章可以作为第十天的补充笔记如果你刚学完栈和队列的基础知识想知道这些题到底在考什么下面的题目拆解和边界条件也能帮你少踩几个坑。1. 第十天的学习起点先搞清楚栈和队列这对“操作受限”的容器1.1 代码随想录为什么把栈和队列安排在字符串、哈希表之后我最初以为前几天的内容是“简单数据结构”栈和队列应该早点讲。但按代码随想录的顺序刷下来才明白前面的数组、链表、哈希表、字符串训练的都是“在开放容器上做遍历和修改”的能力。到了第十天突然出现了两个“操作受限”的线性表你不能随便访问中间元素只能从固定的口子进出。这个“受限”恰恰是它们的价值。数组和链表太自由了自由到很多问题找不到切入点而栈和队列把操作限制死了反而给了你一个明确的解题信号。Carl在代码随想录里反复强调“什么时候想到用栈、什么时候想到用队列”本质上练的就是这种信号识别能力。后面刷到树的遍历、图的搜索、动态规划优化时你会发现当时的“受限”反而成了最快的切入角度。1.2 栈和队列的底层真相容器适配器、deque与复杂度先看一眼基础定义栈是先进后出LIFO只在栈顶插入和删除队列是先进先出FIFO队尾插入、队头删除。这个概念太基础了但有一个底层细节很多人第一次学的时候没注意C STL 里的std::stack和std::queue并不是独立的数据结构而是容器适配器。默认底层容器是deque双端队列也可以用vector或list。你调push、pop实际是转调了底层容器的对应操作。所以栈和队列的“限制”是语义层面的限制不是物理层面的特殊结构。Python 这边也类似栈可以直接用list模拟队列更推荐用collections.deque。注意这里的deque和 C 的deque一个意思都是双端队列头尾都能 O(1) 进出。面试手写队列时最常翻车的点就是用了list的pop(0)那会触发整体搬移复杂度是 O(n)别这么干。复杂度上入栈出栈、入队出队都是 O(1)但查找元素是无序的 O(n)。这个看似显然的事实在后面的高频题里非常关键——单调队列能优化到 O(n)放弃的就是“查找”能力只保留“两端的最大/最小候选”。2. 用栈实现队列、用队列实现栈两道题吃透“出入口”差异2.1 两个栈倒手实现队列transfer时机是唯一难点LeetCode 232 这道题代码随想录里放在栈和队列的第一道。题目很直接用两个栈实现一个队列支持push、pop、peek、empty。核心思路是“倒手”。准备两个栈inStack和outStack。推入元素时一律进inStack弹出时如果outStack为空把inStack里的所有元素依次弹出再压入outStack这样outStack的栈顶就是最早进入的元素。C 实现可以这样class MyQueue { private: stackint inStack, outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); } int pop() { transfer(); int val outStack.top(); outStack.pop(); return val; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };这段代码唯一的难点在transfer的判断条件只有outStack为空时才搬运。如果你每次pop前都搬运顺序立刻乱掉。我当时第一次写把条件写成“如果inStack非空就搬运”结果连续push多个元素后全乱了。画个图模拟一遍就清楚了第一次pop时倒手一批后面只要outStack里还有货就直接从outStack弹出这批顺序已经被倒置过一次再倒就反了。时间复杂度是均摊 O(1)。每个元素最多进inStack一次、出inStack一次、进outStack一次、出outStack一次4 次 O(1) 操作摊到每次访问上就是常数。用均摊分析而不是说严格 O(1)这是我后来面试被追问时补齐的认知。2.2 一个队列原地转圈实现栈把新元素“插队”到队头LeetCode 225 是反过来用队列实现栈。很多人第一反应是“一个不行那就用两个队列”。确实可以用两个队列一个存数据一个做辅助搬运。但更妙的是一队列方案。思路是每次push时先把新元素正常入队然后把新元素之前的所有元素依次“出队再入队”相当于让新元素直接插队到队首。这样pop和top都是 O(1)push是 O(n)。Python 里写出来特别紧凑from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.q手写队列时最容易踩的坑是popleft和pop。deque.pop()默认从尾部弹popleft()才是从头部弹。用list的话pop(0)能用但有 O(n) 搬移成本力扣上数据量小看不出来真到工程里就现原形了。2.3 这两道题结束后我对栈和队列的理解发生了什么变化这两道题表面是“互相实现”本质是在逼你理解一个关键差异栈的出口在尾部队列的出口在头部。用栈实现队列靠的是“倒两次顺序”把尾部出口变成头部出口用队列实现栈靠的是“每来一个新元素就插队到最前”让尾部出口变成头部出口。刷完这两题我最大的收获是以后看到“顺序反转”第一反应就是栈看到“按到达顺序处理”第一反应就是队列。这种条件反射不是背出来的是手写两遍之后长在脑子里的。代码随想录把这组题放在章节开头用意很明显——先通过互相当镜子把容器的行为模型烙进脑子里后面再上真实场景题。3. 括号匹配、相邻重复删除、逆波兰表达式栈的三大主场3.1 有效的括号右括号必须匹配最近的左括号LeetCode 20 是栈的入门必刷题。给你一串只包含()[]{}的字符串判断是否有效。有效性规则里最关键的一条是右括号必须以正确的顺序闭合。什么叫“正确的顺序”就是它必须匹配最近的一个未匹配左括号。这不就是栈的先进后出吗遍历字符串遇到左括号就入栈遇到右括号检查栈顶是否是对应的左括号是就弹出不是就说明不匹配最后再看栈是否为空不为空说明有左括号落了单。代码不复杂但有三个边界值得写进笔记遇到右括号时栈已经空了直接返回 false说明右括号在前。遍历结束后栈不为空返回 false说明右括号不够。三种括号混合时最好用哈希表存配对关系别写三套 if 嵌套。bool isValid(string s) { stackchar st; unordered_mapchar, char pairs { {), (}, {], [}, {}, {} }; for (char c : s) { if (pairs.count(c)) { if (st.empty() || st.top() ! pairs[c]) return false; st.pop(); } else { st.push(c); } } return st.empty(); }很多人觉得这题简单扫描一遍就完事了。但面试里它经常被改编成“括号嵌套深度”“删除最少的括号使其合法”等一系列变体底层都是同一个模型遇到匹配就抵消。把这道题吃透等于给后面的动态规划版本打了个地基。3.2 删除字符串中的所有相邻重复项字符串上的“消消乐”LeetCode 1047 和括号匹配长得不像思路却一模一样。输入abbaca两个相邻的b消掉之后变成aaca相邻的a又能消掉最终结果ca。要处理这种“连锁反应”最自然的就是栈。逐字符压栈当前字符和栈顶相同就把栈顶弹出相当于这对字符抵消了否则入栈。结束之后栈里剩下的字符拼接起来就是答案。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)这道题的启发是消消乐不一定只发生在游戏里。很多字符串处理题看到“相邻”“重复”“回退”这些关键词都要条件反射地想到栈。注意题目说的是“相邻重复”如果改成“删除所有重复字符不管位置”那栈就不好使了得用哈希表统计。这个区分特别重要栈管的是“顺序上的相邻抵消”不管“全局频率统计”。3.3 逆波兰表达式求值一个栈就能搞定后缀表达式LeetCode 150 是栈在表达式求值里的经典应用。逆波兰表达式也叫后缀表达式运算符跟在操作数后面比如1 2 就等于1 2。它最大的好处是不需要括号也不需要优先级规则光靠一个栈就能从左到右算完。规则遇到数字就入栈遇到运算符就弹出栈顶的两个数字先弹出的作为右操作数后弹出的作为左操作数计算后再把结果压回栈。循环结束后栈顶就是答案。写成 Cint evalRPN(vectorstring tokens) { stackint st; for (string t : tokens) { if (t || t - || t * || t /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (t ) st.push(a b); else if (t -) st.push(a - b); else if (t *) st.push(a * b); else if (t /) st.push(a / b); } else { st.push(stoi(t)); } } return st.top(); }有两个坑我一定要说。第一减法除法是有顺序的先弹出的b是右操作数后弹出的a是左操作数写成b - a直接全错。第二整数除法要向零截断。C 的整数除法对负数本身就是向零截断但 Python 的//是向下取整所以 Python 版本遇到除法要写int(a / b)不能直接a // b否则结果为 -1 时会被算成 -2。为什么计算机喜欢后缀表达式因为编译器和解释器根本不需要维护运算符优先级和括号嵌套状态一个栈就搞定了。这也是栈在真实系统里最成功的应用之一只是我们平时写高亮式子看不到这层而已。4. 滑动窗口最大值与前K个高频元素单调队列和优先队列的博弈4.1 暴力解法的瓶颈为什么O(nk)撑不住LeetCode 239 是一道“队列进阶”题给定一个数组和一个大小为 k 的滑动窗口窗口每次右移一格要求输出每个窗口的最大值。暴力解法很好想每个窗口里扫一遍找最大值复杂度 O(nk)。在 k 接近 n 时就是 O(n²)力扣上直接超时。问题本质在于窗口滑动时你既要删除一个左边的元素又要加入一个右边的元素同时还要知道当前窗口的最大值。这个动态维护最大值的过程单靠每次全量扫描肯定浪费。那能不能用一个“队列”来维护窗口能。队列天然符合窗口的滑动方式但普通队列只能保证先进先出不能保证弹出的永远是最大值。于是需要在队列这个容器上增加规则这就是单调队列。4.2 单调队列淘汰永远不会成为最大值的元素单调队列的经典做法是用双端队列deque维护一个从队头到队尾递减的队列队头永远是当前窗口的最大值。窗口滑动时做三件事右端点入队之前把队尾所有小于当前值的元素弹出因为它们年纪比新元素大值还比新元素小永远不可能再成为窗口最大值直接淘汰。如果离开窗口的左端点的值恰好等于队头也就是当前最大值把队头弹出。队头自然就是当前窗口最大值。这里最精妙的是“淘汰”过程。每个元素最多入队一次、出队一次所以整体复杂度是 O(n)不是 O(nk)。用下标存储比存值更严谨这样才能准确判断某个元素是否已经滑出窗口class MonotonicQueue { dequeint dq; // 存下标 vectorint nums; public: MonotonicQueue(vectorint n) : nums(n) {} void push(int idx) { while (!dq.empty() nums[dq.back()] nums[idx]) { dq.pop_back(); } dq.push_back(idx); } void pop(int idx) { if (!dq.empty() dq.front() idx) { dq.pop_front(); // 只有离开的恰好是最大值时才弹 } } int max() { return nums[dq.front()]; } };我第一次写的版本犯了个错把“左端点离开窗口”无条件写成pop_front()。但左端点可能早就被淘汰了队列里根本没有它强行弹出会把更早的、可能还有效的元素弹掉。判断条件必须是“相等才弹”。单调队列的应用远不止这一题。热词里提到的“单调队列优化 DP”本质就是在处理形如“求前一个窗口中符合某种条件的极值”时把 O(k) 的扫描降成均摊 O(1)很多 DP 题从 O(nk) 优化到 O(n) 靠的就是这个思想。4.3 前K个高频元素为什么用小顶堆而不是大顶堆LeetCode 347 要求返回数组里出现频率最高的前 k 个元素。第一步很常规哈希表统计每个元素的频率。第二步就有意思了你有一个频率表怎么高效提出前 k 个最大的最直觉的思路是大顶堆把所有频率都扔进大顶堆然后弹出 k 次。这样复杂度是 O(n log n)能过但不优雅。更优的做法是只维护一个大小为 k 的小顶堆。遍历频率表时堆里不足 k 个直接入堆。堆满了拿当前频率和堆顶比较。堆顶是堆里最小的频率如果当前频率比堆顶大就弹出堆顶、把当前频率入堆。反直觉吧找“最大的前 k 个”反而用的是小顶堆。原因是小顶堆的堆顶是堆内最小元素每次用它做门槛可以随时把最小的踢出去保证留在堆里的始终是最大的 k 个。最终堆里 k 个元素就是答案。C 的priority_queue默认是大顶堆做这题需要手动指定greater这也是一个小坑。vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int x : nums) freq[x]; priority_queuepairint, int, vectorpairint, int, greater pq; // 小顶堆 for (auto [val, cnt] : freq) { pq.push({cnt, val}); if (pq.size() k) pq.pop(); } vectorint ans; while (!pq.empty()) { ans.push_back(pq.top().second); pq.pop(); } return ans; }这题一般归在优先队列/堆的范畴但放在栈和队列章节里也说得通——优先队列本质是一种“带优先级的队列”出队顺序不再由到达时间决定而是由优先级决定。理解了这一点你对“队列”的概念就完成了从数据结构到抽象模型的升级。5. 别搞混三种“队列”数据结构队列、阻塞队列、消息队列5.1 阻塞队列与线程池任务来了放不下怎么办刷题时说的队列很简单FIFOO(1) 进出。但真实工程里有个更常见的队列——阻塞队列BlockingQueue。线程池的workQueue就是典型一堆线程忙着处理任务新任务来了先丢进队列排队。但队列容量是有限的满了怎么办阻塞队列的做法是让生产者线程阻塞住等消费者腾出位置再继续。Java 里常见的ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue区别主要在于边界和语义。比如SynchronousQueue没有容量每个插入操作都必须等待另一个线程的移除操作相当于手递手交接。线程池选哪种队列直接影响拒绝策略和吞吐量这是比刷题深得多的“队列”话题。刷题时理解队列的 FIFO 行为到并发编程里不会自动迁移但你至少能问出正确的问题队列有界还是无界满了是阻塞还是丢弃这个“有界 阻塞”的设计在算法题里就是循环队列加满了的变体在工程里就是背压机制。打好数据结构底子至少能听懂面试官在问什么。5.2 消息队列异步、削峰、解耦里的“队列”不是队列热词里有一批关于 Kafka、RabbitMQ、RocketMQ 的搜索我猜你会好奇这些消息队列和今天学的队列是什么关系答案很直接几乎没有结构上的关系。消息队列MQ是分布式系统里的中间件解决的是“服务间如何可靠地传递消息”的问题。它的核心价值有三个异步下单后发短信丢进 MQ 就返回短信服务慢慢消费。削峰秒杀瞬间流量巨大先全接入 MQ消费端按自己的节奏处理。解耦订单系统和库存系统不直接互相调用都只跟 MQ 打交道一方挂掉不影响另一方。这里的“队列”更多是一个通道或缓冲区的代名词它不一定保证严格的 FIFO更关心的是消息不丢、不重复、能分区、能水平扩展。所以别拿着数据结构队列的 FIFO 特性去套消息队列方向就错了。5.3 Kafka、RabbitMQ、RocketMQ的选择逻辑很多人第一次接触 MQ 选型就懵了我直接给一张简化对照表这是基于工程实践的主观排序不是官方标准维度KafkaRabbitMQRocketMQ吞吐量极高分区并行一般万级高十万级可靠性配置得当可很高但默认有丢风险较高支持生产者/消费者确认很高事务消息强功能特性简单偏日志/流处理路由灵活延迟队列等玩法多事务消息、延迟消息、消息重试完善生态语言Java/Scala流处理强Erlang社区大多语言客户端Java 为主最适合场景大数据、日志采集、事件流中小规模业务消息电商交易、金融级可靠性场景选型别只看名气。Kafka 吞吐确实猛但如果你只是每天几十万条业务消息运维复杂度完全没必要的RabbitMQ 轻量易用功能丰富中小项目足够RocketMQ 在可靠性和事务上很能打Java 生态的团队上手成本低。说白了选 MQ 就是选场景和运维能力不是选“最大最强”。这和刷题选数据结构是一个道理栈能解决的题别非得用哈希表硬怼。6. 从刷题回到现实函数调用栈、栈帧与backtrace6.1 一次函数调用的栈帧里到底装了什么刷题天天用栈但很多人不太清楚“调用栈”这个真实系统里无处不在的栈到底长什么样。当你调用一个函数时操作系统或运行时会在当前线程的栈上分配一块连续区域叫做栈帧stack frame里面保存着返回地址函数执行完要回到哪条指令。函数参数和局部变量。保存的寄存器值保证函数返回后调用者的状态不丢。一些辅助管理信息比如上一个栈帧的地址。递归函数之所以容易爆栈就是因为每递归一层就要压入一个新栈帧栈空间是有限的深度太大自然溢出。这也能解释为什么很多算法题用递归写非常简洁但 n 一大就栈溢出——你用的栈是操作系统给的运行栈不是自己管理的堆空间。6.2 崩溃日志里的backtrace是怎么还原调用链的热词里有“backtrace栈回溯”“arm调用栈回溯”这是系统崩溃分析里极其重要的能力。所谓 backtrace就是把当前线程的调用栈整个翻出来打印出从最内层到最外层的函数调用链。GDB 里的bt命令、Linux 程序崩溃时用backtrace()函数和addr2line配合、Android NDK 崩溃日志里的 tombstone 文件本质都在做同一件事根据栈帧中保存的返回地址一层一层往上找还原出“谁调用了谁”。你平时如果只是写业务代码可能很少直接接触这些东西。但一旦遇到线上崩溃、段错误、栈被写坏能读 backtrace 是最基本的排查能力。理解了栈帧结构你才看得懂崩溃栈里那些地址和函数名的含义。这也是栈这一节延伸到工程层面的最大价值。6.3 栈上变量为什么不能返回堆和栈到底差在哪C/C 初学者最容易踩的一个坑函数返回局部变量的地址然后运行结果莫名其妙变了。原因很简单局部变量存在栈帧里函数一返回栈帧就销毁那块内存不再属于你随时可能被别的内容覆盖。表面上值还在其实是“悬空指针”。而全局静态变量就不一样它存放在静态存储区生命周期从程序启动到程序结束不随函数返回而失效。这就是热词里“栈变量、全局静态变量”背后的差异栈编译期自动分配释放空间小典型几 MB速度快。堆运行期手动分配/释放或 GC空间大速度相对慢有碎片问题。静态区程序启动分配直到结束才释放生命周期全局。刷题时我们用 Python 的列表模拟栈用 C 的std::stack完全不用关心这些内存细节。但真实的栈是要吃内存的递归深度、局部变量大小、函数调用嵌套层数都会直接影响栈空间够不够。这也是为什么工程上大数组要么放全局、要么放堆的原因。7. 第十天的避坑清单与我的内化建议7.1 循环队列的取模、判空判满细节热词里有一句“假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队…”这明显是循环队列的经典考题。用数组实现队列时直接尾部追加、头部删除会浪费大量空间循环队列用取模让front和rear在数组里绕圈入队rear (rear 1) % m出队front (front 1) % m判空length 0判满length m如果不引入length只用两个指针判断空和满就会撞车——满和空时front rear都一样。常见解法是牺牲一个存储单元或者加一个flag标记最近一次操作是入队还是出队。这些细节刷题不一定直接考但“用数组模拟队列”在面试手写时非常常见尤其是消息队列、缓存设计之类的题目里会反复出现。7.2 pop返回void不同语言里的出队接口差异栈和队列的基础操作在不同语言里长得不一样这是个非常影响手写效率的点Cstack::pop()和queue::pop()都返回 void必须先top()/front()取值再pop()。Javapop()直接返回被移除的元素但Deque用poll()和remove()时有空值异常的区别。Pythonlist.pop()默认尾部弹deque.pop()尾部弹popleft()头部弹。这些接口差异在力扣刷题时可能感觉不到但面试现场白板写代码时写错一个pop()返回值是很致命的。我自己的习惯是面试手写前先口头跟面试官确认语言然后在心里默念一遍该语言的接口签名再开始写。7.3 三个建议模型归类、画图模拟、复杂度说理刷完第十天的题目我留下的复习笔记就是三句话分享给你参考第一建立模型归类。看到“逆序处理”“回退”“最近匹配”“相邻抵消”想栈看到“按顺序排队”“滑动窗口”“公平调度”想队列。题目永远在变模型就那几个。第二先画图再写代码。栈和队列的题尤其适合画图模拟尤其是两个栈倒手、单调队列滑动窗口这种画一遍胜过空想十遍。代码写错了回头画图定位也快。第三把复杂度讲出理来。两个栈模拟队列为什么是均摊 O(1)单调队列为什么是 O(n)队列模拟栈为什么 push 是 O(n)这些“为什么”想清楚了面试变形题才能接得住而不是靠背代码。技术面试和工程应用里能说清楚“为什么这样设计”的人跟只会“调 API”的人差别就在这一个层次。我自己的体会是栈和队列这个专题像是一道分水岭前面刷数组、链表练的是“手速”从这道开始练的是“用数据结构的特性去建模问题的能力”。第十天的内容刷完最值得留下的不是代码而是那个“看到问题能条件反射地想到 LIFO 或 FIFO”的肌肉记忆。后面学到二叉树、回溯、动态规划时你再回头看这天的内容会发现它们的身影到处都是。