算法训练营走到第十一天前面那些排序、双指针、二分热身完毕后终于轮到两个看着不起眼、实际无处不在的数据结构栈和队列。很多初学者觉得它们太简单——栈不就是限制只能从一端进出的线性表队列不就是排队嘛。但真到做题和面试手写的时候卡壳的往往就是它们。今天的实战内容我会从原理讲到经典题再到工程里的使用场景把栈和队列一次说透。无论你是刚入门的算法新手还是准备面试需要快速回忆数据结构的人这篇文章都值得跟着过一遍尤其是括号匹配、最小栈、单调队列这几道题几乎是面试手写的固定节目。先给大家提个醒栈和队列不只是“数据结构课里的两个概念”它们是理解递归、回溯、表达式求值、任务调度、消息系统的一把钥匙。今天训练营的核心目标是——看到题目能判断该用栈还是队列能把经典题的模板写熟能在面试时把复杂度讲清楚。所以别急着刷题先把这几道经典吃透后面会越走越顺。1. 为什么要先啃下栈与队列从结构认知到应用场景1.1 栈后进先出的“撤销栈”和生活类比栈的操作其实只有四个字后进先出英文简写 LIFO。你可以把它想成一个只有一个口的箱子放进去的东西要拿出来时一定是后放进去的先拿出来。生活中的例子很直接浏览器里点“后退”回退到的一定是最近访问的页面编辑器里的 CtrlZ 撤销撤销的也是最近一步操作函数嵌套调用时外层函数先调用内层函数先返回这也是栈的顺序。在代码层面栈的常见操作就这么几个push 入栈、pop 出栈、peek 或 top 看一眼栈顶元素、isEmpty 判断为空。这些操作的时间复杂度全是 O(1)这是栈能成为算法题“神器”的根本原因。因为栈能以极低的开销维护“最近发生的状态”所以在括号匹配、表达式求值、函数递归、浏览器历史、深度优先搜索这些场景里它几乎是唯一首选。我见过不少同学觉得栈太“简单”就跳过结果遇到需要用栈维护状态的问题时只会写暴力。比如后文要讲的“下一个更大元素”如果不用单调栈最直接的双重循环复杂度是 O(n^2)一旦 n 到 10 万就挂了。栈的威力不在于它有多少花活而在于它能把暴力枚举中的重复比较压缩掉让每个元素只进栈出栈一次整体变成 O(n)。1.2 队列先进先出的“任务排队”模型队列对应的是先进先出英文缩写 FIFO。这个更好理解你去食堂打饭、在银行取号都是先来的先服务后来的排队等。在操作系统里CPU 的任务调度队列、打印任务队列以及我们常用到的消息队列本质都是“生产者把任务丢进去消费者按顺序取出来”的模型。队列也有几个核心操作入队 enqueue出队 dequeue获取队头 front判断是否为空。这些操作同样是 O(1) 时间完成。队列的最大价值在于它天然适合“按顺序处理”的场景比如广度优先搜索里每一层的节点需要逐个扩展这时候队列就是标准解法。很多树和图的题目只要看到“最短路径”“层序遍历”第一反应就应该是队列。队列还有一种变形叫双端队列也就是两端都能进出。这个结构比普通队列更灵活后面要讲的单调队列就会用到它。还有循环队列它用数组实现时可以避免频繁搬移元素空间利用率也更高。今天的实战里我会重点演示循环队列的实现细节因为面试中让手写循环队列的概率不低而且能考查你对数组下标取模的理解。1.3 它们在算法面试和工程里的地位栈和队列是算法面试的“基础题守门员”。为什么这么说因为这两类题看起来不难却能快速检验一个人的基本功边界条件处理得干不干净、复杂度分析清不清楚、代码风格稳不稳定。很多公司的手写环节喜欢出“用两个栈实现队列”或者“最小栈”就是因为这几个题目短小精悍能在几分钟内看出候选人是否真写过代码。更重要的是栈和队列是很多高级算法的地基。比如深度优先搜索的递归实现本质就是系统帮你维护了一个调用栈像 Tarjan 算法求强连通分量需要显式地使用栈维护访问顺序回溯搜索里的“恢复现场”也是对栈的一种直觉应用KMP 算法虽然核心不是栈但它优化的思想也是“利用已经匹配的信息”这和单调栈“利用单调性压缩冗余比较”的思路如出一辙。把今天这些题练透你后面学树、图、动态规划的时候会发现很多套路都是通的。2. 栈的经典实战括号匹配、最小栈与单调栈2.1 括号匹配从暴力到栈的优化括号匹配是栈的入门第一题题目描述很简单给定一个只包含(、)、{、}、[、]的字符串判断括号是否合法。合法条件有两个左括号必须有对应类型匹配的右括号而且顺序不能错比如([)]就是非法的虽然每个左括号都能找到右括号但类型交叉了。暴力做法是每次遇到右括号就往左找最近的左括号记录哪些已经被匹配复杂度是 O(n^2)而且写起来很绕。用栈的思路就清爽了遇到左括号就入栈遇到右括号就检查栈顶是不是对应的左括号如果是就弹出否则直接判定不合法。遍历结束后栈必须是空的说明所有左括号都被匹配了。def is_valid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack这里要注意两个细节。第一个遇到右括号时先判断not stack防止空栈时取栈顶报错第二个用字典建立右括号到左括号的映射比用 if-else 区分三种括号更简洁也不容易漏掉类型。复杂度是 O(n)空间最坏也是 O(n)因为全是最内层嵌套的左括号时栈里要存 n/2 个元素。这道题衍生出来的变体也很多比如要求打印“最短补全括号数”或者判断带通配符的括号字符串核心都离不开“右括号必须消掉最近的左括号”这个思想。如果把它想成“消消乐”规则就是类型匹配的一对括号互相抵消那么栈就是玩这个游戏最自然的数据结构。2.2 最小栈以空间换时间的典型思路第二道经典题是最小栈MinStack。要求设计一个栈除了 push、pop、top 之外还要支持 getMin能在 O(1) 时间内取到当前栈的最小值。很多人第一反应是维护一个变量记录全局最小值但一旦最小元素被 pop 掉你就不知道第二小的值是谁了。所以正确思路是“用额外的栈同步记录每一步的最小值”。具体做法是每次 push 元素时把“当前栈中最小值”也 push 进辅助栈。因为栈的特点是后进先出所以辅助栈的栈顶永远是当前所有元素的最小值pop 的时候两个栈同时 popgetMin 直接读辅助栈栈顶即可。class MinStack: def __init__(self): self.stack [] self.min_stack [] def push(self, val: int) - None: self.stack.append(val) if not self.min_stack or val self.min_stack[-1]: self.min_stack.append(val) else: self.min_stack.append(self.min_stack[-1]) def pop(self) - None: self.stack.pop() self.min_stack.pop() def top(self) - int: return self.stack[-1] def get_min(self) - int: return self.min_stack[-1]这里有个容易踩的坑辅助栈在 push 时比较条件是val self.min_stack[-1]还是。如果只用那么出现两个相等的最小值时pop 掉一个辅助栈里可能找不到另一个最小值了。要么用保证每个状态都有最小值要么像我上面代码那样每次 push 都把当前最小值同步写入 min_stack这样逻辑最简单也不用担心相等元素的问题。这道题的核心价值在于展示“空间换时间”的思路。辅助栈额外用了 O(n) 空间但换来了 getMin 的 O(1) 时间。面试里经常追问能不能不用辅助栈有一种压缩栈的做法栈里存最小值和当前值的差值但代码容易绕且需要考虑数值溢出。我个人建议先把同步辅助栈的版本写熟再去研究花式优化基础题求稳比求炫更重要。2.3 单调栈下一个更大元素的套路单调栈是栈里面最值得玩味的进阶用法也是面试常客。它的思想是维护一个栈内元素单调递增或单调递减的栈利用这个单调性在遍历过程中一次性得到每个元素的“下一个更大元素”“下一个更小元素”等信息。以“下一个更大元素”为例给定数组[2, 1, 4, 3]要求返回每个元素右边第一个比它大的数不存在的用 -1 表示。暴力思路是双重循环对每个元素向右找复杂度 O(n^2)。单调栈的做法是从左往右遍历数组维护一个“栈底大、栈顶小”的单调递减栈。当新元素大于栈顶元素时说明栈顶元素的“下一个更大元素”就是当前新元素于是将栈顶弹出并记录答案然后继续比较新栈顶直到当前元素能入栈保持单调性为止。def next_greater_element(nums): n len(nums) res [-1] * n stack [] # 存下标 for i in range(n): while stack and nums[i] nums[stack[-1]]: idx stack.pop() res[idx] nums[i] stack.append(i) return res这里有一个关键选择栈里存下标而不是直接存值。为什么因为后续可能还要用到元素位置信息比如计算“距离下一个更大元素的距离”时如果有下标就能直接算出索引差。存下标是一种更通用的写法很多题都依赖这一点。单调栈的复杂度分析是精髓每个元素最多入栈一次、出栈一次所以总时间复杂度是 O(n)空间 O(n)。这种“看着有两层循环其实是摊还 O(1)”的感觉一开始可能不太适应但多写几题就习惯了。掌握了这个模板像“每日温度”“接雨水”“柱状图中最大的矩形”都可以套用。尤其是“接雨水”那道题用单调栈能把每个“凹槽”的面积算清楚比双指针思路更通用。做这类题时我建议先在纸上画一下数组和栈的变化过程你会发现所谓单调栈其实是在模拟一个“淘汰弱小元素”的过程。3. 队列的经典实战循环队列、双端队列与滑动窗口3.1 数组实现循环队列rear 与 length 的配合循环队列是队列的数组实现进阶版也是数据结构课里经典的“假溢出”问题解法。用普通数组实现队列时队头元素出队后前面的空间就浪费了如果不断入队出队很快队尾会到达数组末尾即使前面有空位也没法再入队。循环队列的思路是把数组首尾相连队尾指针绕回开头继续用空间。热词里有一句话描述得特别标准“假设以数组 q[m] 存放循环队列中的元素同时以 rear 和 length 分别指示环形队列中的队尾元素位置和当前队列长度。”这里的 rear 是队尾位置length 是队列实际元素个数。用这种表示方式队头位置可以算出来队头下标等于(rear - length m) % m。这是一个很经典的模运算计算。用 length 而不是 front 的好处是判断队列空和满非常直观length 等于 0 就是空count 等于 m 就是满不会出现 front 和 rear 相等时到底是空还是满的歧义。我用 Python 给你写一个精简版重点看下标计算class MyCircularQueue: def __init__(self, k: int): self.q [0] * k self.cap k self.head 0 self.size 0 def en_queue(self, value: int) - bool: if self.is_full(): return False tail (self.head self.size) % self.cap self.q[tail] value self.size 1 return True def de_queue(self) - bool: if self.is_empty(): return False self.head (self.head 1) % self.cap self.size - 1 return True def front(self) - int: if self.is_empty(): return -1 return self.q[self.head] def rear(self) - int: if self.is_empty(): return -1 tail (self.head self.size - 1) % self.cap return self.q[tail] def is_empty(self) - bool: return self.size 0 def is_full(self) - bool: return self.size self.cap很多同学写循环队列时会疑惑入队时为什么不用维护一个独立的 tail 指针原因是我用 size 和 head 推导 tail新元素要放的位置是head size因为当前队列尾的下标是head size - 1。这么做少维护一个变量也减少了出错机会。出队时只需移动 head 并让 size 减一空间上被跳过的位置会在后续入队时被重新利用。这里要特别强调取模的坑如果只在循环时不取模等下标超出数组范围再取模会导致中间状态很乱。正确做法是所有涉及下标位移的运算都及时% cap比如(head size) % cap这样才能保证下标始终落在[0, cap - 1]。另一个常见错误是出队时忘记判断空、入队时忘记判断满一旦操作非法就直接返回 false避免数组越界。循环队列几乎必考就是因为能同时考察数组、取模、边界条件三件事。3.2 用栈实现队列用队列实现栈互相模拟用两个栈实现队列是面试特别喜欢出的“设计题”。思路很简单用两个栈一个专门负责入队一个专门负责出队。入队时直接 push 进入栈 in_stack出队时如果 out_stack 不为空则直接弹出否则把 in_stack 里所有元素倒到 out_stack再弹出。为什么这样可行因为栈的倒序在两次翻转后恢复成原始顺序。举个例子入队顺序 1、2、3in_stack 里是 [1,2,3]倒到 out_stack 后是 [3,2,1]弹出的是 1正好是最先入队的元素符合队列的先进先出。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x: int) - None: self.in_stack.append(x) def pop(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self) - bool: return not self.in_stack and not self.out_stack这个解法的均摊复杂度很值得分析每个元素会被 push 进 in_stack 一次从 in_stack 弹到 out_stack 一次再从 out_stack 弹出一次总共三次 O(1) 操作所以均摊时间复杂度是 O(1)。这里有个小细节peek和pop都要先保证 out_stack 里是“倒好顺序”的数据最好抽一个公共函数amortize()避免代码重复。面试时如果你写了两遍相同的翻转逻辑面试官大概率会提醒你重构。反过来用队列实现栈也不难但有小陷阱。最朴素的做法是入栈时直接入队出栈时把队列里除了队尾以外的所有元素重新入队到队尾然后弹出最后一个元素。这样队尾元素就是栈顶每次出栈都相当于“把队列转一圈”。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) def pop(self) - int: for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) return self.q.popleft() def top(self) - int: return self.q[-1] def empty(self) - bool: return not self.q注意这里的top()直接用self.q[-1]因为 Python 的 deque 可以 O(1) 访问末尾但在其他只允许访问队头的语言里需要先执行一次“旋转”再把元素放回去。题目有时会限制“只能使用标准队列操作”那top就要用临时变量实现。这些设计题最重要的不是代码多复杂而是你能不能讲清楚“为什么这么做不会打乱顺序”。3.3 滑动窗口最大值与单调队列滑动窗口最大值是队列章节最经典的一道题题目是给定数组 nums 和窗口大小 k窗口从数组左端滑到右端每移动一次返回窗口内最大值。暴力做法是每滑动一次就扫描窗口里的 k 个元素整体复杂度 O(nk)一旦数据规模上来就没法用。单调队列解法是这道题的灵魂。维护一个双端队列里面存的是数组下标并且保证这些下标对应的值从队头到队尾严格递减。换句话说队头永远是当前窗口的最大值。当新元素入队时从队尾把所有小于等于新元素的值都弹出因为它们永远不可能成为之后窗口的最大值了然后把新元素下标入队最后检查队头下标是否已经滑出窗口如果滑出就弹出。from collections import deque def max_sliding_window(nums, k): dq deque() res [] for i, v in enumerate(nums): while dq and nums[dq[-1]] v: dq.pop() dq.append(i) if dq[0] i - k: dq.popleft() if i k - 1: res.append(nums[dq[0]]) return res这段代码里有几个点要反复确认。第一窗口的淘汰条件是dq[0] i - k而不是因为下标差距等于 k 时队头元素已经不在窗口范围内了。第二为什么nums[dq[-1]] v要用因为如果只弹出 v的那么遇到相等值时会保留旧下标这本身没错但用会让新元素顶掉旧元素窗口内更新、更新鲜的下标更不可能被误删代码也更省心。第三什么时候开始记录结果下标从 0 开始所以当i k - 1时当前窗口才完整。单调队列的时间复杂度是 O(n)因为每个下标最多入队一次、出队一次。空间复杂度 O(k)因为队列里最多同时存放 k 个下标。这道题和单调栈是一个思想家族单调栈处理的是“前一个/后一个更大元素”单调队列处理的是“滑动窗口里的极值”。理解“单调性如何淘汰冗余信息”比背模板重要得多只要把这两个题放在一起对比你对“单调”这个概念的理解会上一个台阶。4. 工程场景中的栈与队列函数调用、阻塞队列、消息队列4.1 函数调用栈与栈帧很多人学栈的时候觉得它很抽象但只要你写过程序其实每天都在和栈打交道。以 C 语言为例每次进入一个函数系统都会在“调用栈”上分配一块区域叫栈帧。栈帧里保存了函数的局部变量、参数、返回地址以及保存的寄存器现场。当一个函数调用另一个函数时新的栈帧被压入栈顶当被调用函数返回时栈帧被弹出控制权交还给调用者。这种后进先出的顺序就是栈的本性。热词里的“栈帧形成过程”“backtrace栈回溯”“arm调用栈回溯”其实都指向同一个话题当程序崩溃或异常时调试器借助调用栈来还原现场。栈回溯就是沿着调用栈的栈帧逐个打印或解析出函数调用路径让开发者快速定位崩溃发生在哪个函数链路上。如果你写过嵌入式、写过 C一定见过类似backtrace()的函数它本质上就是在读栈帧里的返回地址。理解调用栈对算法学习也有帮助。递归函数之所以可能栈溢出就是因为每层递归都要压入一个栈帧深度太大就撑爆了。很多“递归改非递归”的题目比如二叉树的中序遍历其实是用显式的栈模拟了系统调用栈。所以别把栈只当作刷题工具它是编程语言运行时的重要机制。我建议你在本地用 gdb 或 IDE 调试点断点看一次“调用堆栈”窗口的变化所有对栈的疑问会一下子落地。4.2 线程池里的阻塞队列怎么选队列在并发编程里出场率极高尤其是线程池。线程池的核心思想是任务先放到一个队列里空闲线程从队列头部取任务执行。如果队列满了新任务要么阻塞等待要么被拒绝如果队列空了工作线程要阻塞等待新任务。这个用来存任务的队列通常就是一个阻塞队列Blocking Queue。工程中常见的阻塞队列有几个选择各有用途。无界队列如LinkedBlockingQueue默认容量很大任务可以无限入队但也可能因为任务积压导致内存耗尽。有界队列如ArrayBlockingQueue指定最大容量满了之后执行拒绝策略能保护系统不被突发的任务洪峰冲垮。还有SynchronousQueue它不存储元素每个入队操作必须等待一个出队操作线程池用它可以实现“直接提交任务给线程处理”的效果。面试中总问“线程池的阻塞队列怎么选”其实就是在考察你对流量模型的理解如果你的系统允许短暂排队有界队列更安全如果要求低延迟且线程数不固定可能选择 SynchronousQueue 更合适。热词里还出现了“C原子操作与无锁队列”这是队列在高性能场景下的一种进阶形态。无锁队列通过原子变量和 CAS 操作实现多线程安全避免了锁竞争但实现难度很大容易出 ABA 问题。学习栈和队列的时候不需要深入这些但知道有这类工程存在能帮你建立“数据结构理论到工程实践”的连接。工程里遇到性能瓶颈时第一步永远是分析队列长度、入队出队频率、消费速度而不是一上来就上无锁优化。4.3 消息队列重复消费幂等设计还有一个和队列强相关的常见工程问题消息队列的重复消费。在实际系统中生产者把消息投递到消息队列消费者按照先进先出的顺序处理看起来和队列模型完全一致。但分布式环境下消费者处理完消息后还没来得及提交确认系统就可能宕机重启消息会被重新投递一次这就导致同一条业务消息被处理两次。解决重复消费的核心办法是“幂等设计”让同一个操作执行一次和执行多次产生相同的结果。比如写入订单表前先根据消息里的唯一业务 ID 查一下是否已经处理过或者用数据库的唯一索引约束让重复插入直接失败忽略。这个问题的本质是“队列消费不是天然一次性的你需要自己保证幂等”。学数据结构的时候我们默认队列里的元素被消费一次就没了但工程里分布式队列的“至少一次投递”和“精确一次消费”是两回事。能把队列模型和工程现实做区分是区分“会背概念”和“真懂系统”的分水岭。对了热词里还有个“徐庶 简单的消息队列”听起来像是某个开源项目或课程里的简化版消息队列。其实实现一个简单的消息队列核心不就是“生产者入队、消费者出队”吗只不过要加上持久化、确认机制、多消费者协调这些细节。如果你真想理解消息队列可以先在单机内存里用队列实现一个生产者消费者模型再慢慢加并发控制这条路径比直接看 RocketMQ 源码友好得多。5. 常见问题排查与刷题避坑实录5.1 空栈、队满、下标索引三个高频雷刷题多了你会发现栈和队列的报错多半出在三个地方空栈、队满、下标越界。先说空栈很多初学者在pop或取栈顶前忘了判断isEmpty一遇到空输入就崩溃。解决方法是把“先判断再操作”写成肌肉记忆尤其是出现“连续两个操作”时比如先peek再pop一定要在中间状态里保持判断。队列的front和rear操作同理合法队列为空时通常返回 -1 或抛异常但不能让程序直接崩溃。队满问题集中在循环队列和阻塞队列上。手写循环队列时一定要先算清楚队列容量和 size 的关系。有些题目把数组长度设为 k 但实际只能放 k 个元素那你判断满的条件就是size k如果题目要求“最多存放 k-1 个元素”那是为了用front rear区分空和满这时判断逻辑要跟着改。强烈建议大家把循环队列的“用 front 和 size 表示空满”和“用 front 和 rear 表示空满”两种写法都练一遍面试官很喜欢在这个地方挖坑。下标索引问题最隐蔽。比如单调队列存的是下标窗口移动后忘记更新队头下标单调栈里用值比较却存下标导致结果记录错位。我自己的调试经验是遇到下标相关的问题先打印出来看“栈/队列里现在有哪些下标”“对应的值是多少”一遍就能发现问题。记住数据结构里存的是值还是下标决定了后续逻辑能查到什么信息。这是一个设计决策不是随便选的。5.2 复杂度估算陷阱栈和队列的操作看似都是 O(1)但实际题目里很容易写出“假 O(n)”。最大陷阱就是“在循环里进行队列扫描”。比如用普通列表模拟队列出队时如果删除头部元素Python 的list.pop(0)或者 C 的vector.erase()都是 O(n) 的一旦你在窗口滑动中频繁调用整体复杂度就成 O(n²) 了。正确做法是用内置的collections.deque它的两端的插入删除都是 O(1)或者用循环队列自己管理下标。另一个复杂度陷阱是“均摊”这个概念。用两个栈实现队列时单次pop可能触发一整批元素的搬移最坏 O(n)但因为每个元素只会被搬移一次均摊下来还是 O(1)。面试时如果只答“pop 是 O(1)”很容易被追问你应该主动说“单次最坏 O(n)但均摊 O(1)因为每个元素只进出两次”。这样回答既准确又显得你懂底层。同样单调栈的 while 循环乍一看是嵌套的但每个元素出栈一次所以总体是 O(n)这个摊还分析一定要会。5.3 我的压箱底刷题经验栈和队列的题刷多了我发现一个特别实用的经验做题前先在纸上“演栈”。拿括号匹配来说你手写一遍([{}])和([)]的入栈出栈过程立刻就能明白为什么栈能处理顺序问题。别怕浪费时间画图是最快的调试方式。其次是“调试打印法”在关键位置加打印输出比如单调栈里打印每次弹出和入栈的下标能让你立刻看清算法的每个动作。这个方法比断点调试还直观尤其适合在线刷题场景。第三个经验是“模板归类”。栈和队列不是零散的知识点它们有清晰的套路括号匹配、表达式求值、最小栈是“状态保存”类单调栈、单调队列是“单调性优化”类用栈实现队列、用队列实现栈是“结构模拟”类循环队列是“数组实现”类。每做完一道题把它归到某一类下次遇到类似题就能快速联想。我见过不少同学刷了上百道题还是慌乱就是因为没有做这个归类动作。最后再分享一个小技巧学栈和队列的时候不要把精力全放在“难题炫技”上先把最基础的手写写法练到“闭着眼都能写对”。比如括号匹配、用两个栈实现队列、循环队列入队出队这三件事你如果能做到 5 分钟内无 bug 写完面试的基本盘就稳住了。基础不牢的时候去啃“接雨水”“最大矩形”只会收获挫败感先把简单题变成肌肉记忆再往上够难度这个顺序永远不会错。