栈和队列大概是数据结构里最容易被低估的两个东西。很多人翻到这一章扫一眼先进后出先进先出觉得概念五分钟就懂了然后直接跳到树和图。结果到了后面做表达式求值、写BFS、处理滑动窗口、设计缓存淘汰策略的时候才发现卡住自己的恰恰是这两个最简单的结构。我当年也是这样第一遍学的时候觉得没啥第二遍做题才发现栈和队列真正的难点根本不在定义而在于你能不能识别出这道题该用栈还是该用队列以及能不能用它们把一团乱麻的逻辑理顺。这篇内容就是围绕栈和队列的复习展开的。我会把这两个结构的核心原理、底层实现方式、典型应用场景、手写代码的关键细节以及刷题时最容易踩的坑全部拆开讲一遍。不管你是正在准备考试的学生还是工作几年后想回头补基础的开发者或者只是被某道算法题卡住了想找个系统梳理这篇应该都能帮上忙。我尽量不写成教科书那种干巴巴的定义罗列而是按照一个实际复习者的思路从是什么到怎么用到哪里容易错一步步展开。1. 栈和队列到底在解决什么问题1.1 从生活场景理解两种结构的本质差异先别急着看定义。你想象一个场景食堂里叠在一起的一摞盘子你每次拿盘子只能从最上面拿放盘子也只能放在最上面。这就是栈——最后放上去的盘子最先被拿走也就是后进先出LIFO, Last In First Out。再想象另一个场景奶茶店排队你先到的先点单后来的人排在队尾店员每次叫号都从队头叫。这就是队列——最先来的最先被服务也就是先进先出FIFO, First In First Out。这两个场景看起来简单到不需要解释但它们背后隐藏着一个非常关键的设计思想对操作位置进行限制。栈只允许在一端栈顶进行插入和删除队列允许在一端插入队尾、另一端删除队头。正是这种限制让它们在某些特定问题上变得极其高效。你可能会问既然数组和链表什么位置都能操作为什么还要专门搞两个受限的结构答案在于限制带来秩序。当你把操作范围缩小到一端或两端时很多复杂的顺序问题就变得可以追踪、可以预测了。比如函数调用、括号匹配、撤销操作这些场景天然就带有最近的先处理的特征用栈来建模几乎是零成本的。1.2 为什么复习时容易轻视这两个结构我观察过很多人的复习习惯包括我自己早期也是这样翻开数据结构教材看到栈和队列这一章觉得概念简单、代码也短就快速翻过去了。这种轻视主要来自两个原因。第一个原因是概念门槛低。栈和队列的定义确实简单不需要像红黑树那样理解旋转和着色也不需要像图那样理解各种遍历策略。你五分钟就能给别人讲清楚什么是栈。但能讲清楚定义和能在复杂问题中灵活运用之间差了十万八千里。第二个原因是单独考察少。考试或者面试里很少会直接问你请写出栈的定义更多是把它嵌入到一个更大的问题里。比如判断一个字符串中的括号是否合法考的是栈用两个栈实现一个队列考的是栈和队列的组合二叉树的层序遍历考的是队列。如果你只记住了定义遇到这些题就会反应不过来。所以复习栈和队列的正确姿势不是背定义而是建立问题特征到结构选择的映射关系。当你看到最近匹配嵌套回退这些关键词时脑子里应该自动弹出栈当你看到按层按顺序排队广度优先时应该自动弹出队列。这个映射关系才是复习的核心产出。1.3 复习栈和队列需要抓住的三条主线我把栈和队列的复习拆成三条主线后面所有内容都围绕这三条线展开。第一条主线是底层实现。栈和队列都可以用数组实现也可以用链表实现。数组实现和链表实现在性能、内存、边界处理上各有差异理解这些差异才能在实际编码时做出正确选择。第二条主线是典型应用。栈的经典应用包括括号匹配、表达式求值、函数调用模拟、单调栈等队列的经典应用包括层序遍历、BFS、滑动窗口、任务调度等。每一个应用都对应一类问题模式掌握这些模式比记住代码模板更重要。第三条主线是组合与变形。实际题目很少单独考一个裸的栈或裸的队列更多是考它们的组合比如用两个栈实现队列、用两个队列实现栈、单调队列、循环队列等。这些变形才是真正拉开差距的地方。2. 栈的核心原理与手写实现细节2.1 栈的基本操作与时间复杂度分析栈的核心操作只有四个push入栈、pop出栈、peek查看栈顶元素、isEmpty判断是否为空。所有操作都只涉及栈顶一个位置所以用数组或链表实现时时间复杂度都是O(1)。这是栈最大的优势——不管栈里有多少元素入栈和出栈的速度都是一样的。但这里有一个容易被忽略的细节用数组实现栈时如果数组容量固定当栈满时需要进行扩容。扩容操作本身是O(n)的但均摊到每次push操作上平均时间复杂度仍然是O(1)。这个均摊分析的思路在面试中经常被问到你需要能解释清楚虽然偶尔会有一次O(n)的扩容但扩容频率随着容量增大而降低总体均摊下来每次push还是O(1)。用链表实现栈时通常把链表头部作为栈顶因为头部插入和删除都是O(1)。如果用尾部作为栈顶单链表需要遍历到尾部才能插入就变成O(n)了。所以链表实现栈时栈顶一定对应链表头部这是一个必须记住的细节。2.2 数组实现栈的完整代码与边界处理下面是用数组实现栈的完整代码我加上详细注释说明每个边界处理的原因。class ArrayStack: def __init__(self, capacity10): self._data [None] * capacity # 底层数组 self._capacity capacity # 当前容量 self._size 0 # 栈中元素个数 def push(self, value): if self._size self._capacity: self._resize(2 * self._capacity) # 扩容为原来的两倍 self._data[self._size] value self._size 1 def pop(self): if self._size 0: raise IndexError(pop from empty stack) value self._data[self._size - 1] self._data[self._size - 1] None # 释放引用帮助垃圾回收 self._size - 1 return value def peek(self): if self._size 0: raise IndexError(peek from empty stack) return self._data[self._size - 1] def is_empty(self): return self._size 0 def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self._size): new_data[i] self._data[i] self._data new_data self._capacity new_capacity这段代码里有几个值得注意的点。第一pop操作里把被移除的位置设为None这是为了帮助垃圾回收器释放对象引用在Python里尤其重要因为列表会持有对象的引用。第二扩容策略是翻倍而不是加固定值这样均摊时间复杂度才能保持O(1)。如果每次扩容只加1那均摊下来每次push就变成O(n)了。第三peek和pop都要检查空栈这是最常见的运行时错误来源。注意很多人在实现栈时忘记处理空栈的pop和peek导致程序在边界情况下崩溃。实际编码中空栈检查应该是条件反射级别的操作。2.3 链表实现栈的取舍与注意事项链表实现栈的代码更简洁因为不需要考虑扩容。class LinkedStack: class _Node: def __init__(self, value, next_nodeNone): self.value value self.next next_node def __init__(self): self._head None self._size 0 def push(self, value): self._head self._Node(value, self._head) self._size 1 def pop(self): if self._head is None: raise IndexError(pop from empty stack) value self._head.value self._head self._head.next self._size - 1 return value def peek(self): if self._head is None: raise IndexError(peek from empty stack) return self._head.value def is_empty(self): return self._head is None链表实现栈的优势是不需要预先分配容量也不会浪费内存。但劣势是每个节点都有额外的指针开销内存利用率不如数组。另外链表节点在内存中不连续缓存命中率低实际运行速度可能比数组实现慢。所以选择哪种实现取决于你的具体场景如果对内存敏感且元素数量可预估用数组如果元素数量波动大且频繁增删用链表。3. 队列的核心原理与手写实现细节3.1 普通队列的痛点与循环队列的引入队列的基本操作是enqueue入队和dequeue出队。用数组实现普通队列时如果队头在数组索引0的位置每次出队后都需要把后面所有元素往前挪一位这样dequeue的时间复杂度就变成O(n)了。这显然不可接受。解决办法是不移动元素而是移动队头指针。队头指针向后移动队尾指针也向后移动。但这样会带来一个新问题数组前面的空间被浪费了队尾指针很快会到达数组末尾即使前面还有空位也无法继续入队。这就是假溢出现象。循环队列就是为解决假溢出而生的。它的核心思想是当队尾指针到达数组末尾时让它绕回到数组开头形成一个逻辑上的环。判断队列满和队列空的条件也变得微妙起来这是循环队列最容易出错的地方。3.2 循环队列的满空判断与代码实现循环队列最经典的坑就是当front rear时到底是队列空还是队列满如果只用front和rear两个指针这两种情况无法区分。常见的解决方案有两种。第一种是牺牲一个存储单元当(rear 1) % capacity front时认为队列满当front rear时认为队列空。这样队列最多只能存capacity - 1个元素。第二种是额外维护一个size变量记录当前元素个数这样队列满和队列空都能准确判断且不浪费空间。我推荐第二种方案因为它更直观也不浪费空间。下面是完整实现。class CircularQueue: def __init__(self, capacity): self._data [None] * capacity self._capacity capacity self._front 0 # 队头索引 self._size 0 # 当前元素个数 def enqueue(self, value): if self._size self._capacity: raise OverflowError(queue is full) rear (self._front self._size) % self._capacity self._data[rear] value self._size 1 def dequeue(self): if self._size 0: raise IndexError(dequeue from empty queue) value self._data[self._front] self._data[self._front] None self._front (self._front 1) % self._capacity self._size - 1 return value def front(self): if self._size 0: raise IndexError(queue is empty) return self._data[self._front] def is_empty(self): return self._size 0 def is_full(self): return self._size self._capacity这段代码里队尾索引不是单独维护的而是通过(front size) % capacity计算出来的。这样做的好处是不需要额外维护rear指针减少了状态不一致的风险。每次入队和出队只需要更新front和size两个变量逻辑更清晰。提示循环队列的取模运算%是核心所有涉及索引移动的地方都必须取模否则就会越界。这是手写循环队列时最容易漏掉的地方。3.3 链表实现队列与双端队列的扩展链表实现队列时需要同时维护队头指针和队尾指针。入队在队尾进行出队在队头进行两者都是O(1)。如果只维护队头指针入队就需要遍历到尾部变成O(n)所以队尾指针是必须的。class LinkedQueue: class _Node: def __init__(self, value, next_nodeNone): self.value value self.next next_node def __init__(self): self._head None # 队头 self._tail None # 队尾 self._size 0 def enqueue(self, value): new_node self._Node(value) if self._tail is None: self._head new_node self._tail new_node else: self._tail.next new_node self._tail new_node self._size 1 def dequeue(self): if self._head is None: raise IndexError(dequeue from empty queue) value self._head.value self._head self._head.next if self._head is None: self._tail None # 队列变空时tail也要置空 self._size - 1 return value这里有一个非常容易忽略的细节当出队后队列变为空时必须把_tail也置为None。如果不这样做_tail会指向一个已经被移除的节点下次入队时就会出错。这个bug在实际编码中很隐蔽因为队列非空时一切正常只有队列变空再重新入队时才会暴露。双端队列Deque是队列的扩展允许在两端进行插入和删除。Python的collections.deque就是双端队列的高效实现。双端队列在滑动窗口最大值、回文检查等场景中非常有用后面会详细讲。4. 栈和队列的经典应用场景拆解4.1 括号匹配栈的入门级应用括号匹配是栈最经典的应用没有之一。问题是这样的给定一个只包含(、)、[、]、{、}的字符串判断括号是否合法匹配。解题思路很直接遇到左括号就入栈遇到右括号就检查栈顶是否是对应的左括号。如果是弹出栈顶如果不是或者栈为空说明不匹配。最后检查栈是否为空为空则全部匹配。def is_valid(s): stack [] mapping {): (, ]: [, }: {} for char in s: if char in ([{: stack.append(char) else: if not stack or stack[-1] ! mapping[char]: return False stack.pop() return len(stack) 0这段代码看起来简单但有几个细节值得说。第一用字典做右括号到左括号的映射比写一堆if-else优雅得多。第二遇到右括号时先检查栈是否为空再检查栈顶是否匹配顺序不能反否则空栈时访问stack[-1]会报错。第三最后必须检查栈是否为空因为可能存在左括号多余的情况比如(()。注意括号匹配的变体很多比如最多删除一个字符使括号合法、括号生成等。核心思路都是围绕栈展开的掌握基础版本后变体只是在这个基础上加条件。4.2 表达式求值栈的进阶应用表达式求值比括号匹配复杂一个量级因为它涉及运算符优先级和两种栈的配合。以中缀表达式3 4 * 2为例人一眼就能看出先算乘法再算加法但计算机需要一套明确的规则。标准解法是用两个栈一个操作数栈一个运算符栈。遍历表达式时遇到数字直接入操作数栈遇到运算符时如果当前运算符优先级不高于栈顶运算符就先弹出栈顶运算符进行计算直到当前运算符可以入栈为止。def evaluate(expression): def apply_op(op, b, a): if op : return a b if op -: return a - b if op *: return a * b if op /: return a // b precedence {: 1, -: 1, *: 2, /: 2} nums [] ops [] i 0 while i len(expression): char expression[i] if char.isdigit(): num 0 while i len(expression) and expression[i].isdigit(): num num * 10 int(expression[i]) i 1 nums.append(num) continue elif char (: ops.append(char) elif char ): while ops and ops[-1] ! (: nums.append(apply_op(ops.pop(), nums.pop(), nums.pop())) ops.pop() # 弹出左括号 elif char in precedence: while ops and ops[-1] ! ( and precedence[ops[-1]] precedence[char]: nums.append(apply_op(ops.pop(), nums.pop(), nums.pop())) ops.append(char) i 1 while ops: nums.append(apply_op(ops.pop(), nums.pop(), nums.pop())) return nums[0]这段代码有几个关键点。第一处理多位数时需要循环读取连续数字不能只读一位。第二遇到右括号时要一直计算到遇到左括号为止然后把左括号弹出。第三运算符入栈前要比较优先级优先级高的先算。第四注意apply_op的参数顺序先弹出的是右操作数后弹出的是左操作数减法和除法对顺序敏感搞反了结果就错了。4.3 层序遍历与BFS队列的主场队列在树和图的遍历中扮演着不可替代的角色。二叉树的层序遍历就是最典型的例子从上到下、从左到右依次访问每一层的节点。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这里的关键技巧是在每层开始时记录队列的长度level_size然后只处理这么多节点。这样就能保证每次循环处理的是同一层的所有节点不会混入下一层的节点。这个技巧在几乎所有层序遍历的变体中都会用到比如二叉树的右视图、二叉树的最大宽度等。BFS广度优先搜索本质上就是层序遍历在图上的推广。图的BFS需要一个visited集合来避免重复访问其他逻辑和树的层序遍历几乎一样。BFS的一个重要性质是在无权图中BFS第一次访问到某个节点时走过的路径就是最短路径。这个性质让BFS成为解决最短路径问题的首选方法。4.4 单调栈与单调队列进阶利器单调栈和单调队列是栈和队列的进阶用法也是面试中的高频考点。它们的核心思想是在栈或队列中维护一个单调递增或单调递减的序列从而在O(n)时间内解决一些看起来需要O(n²)的问题。单调栈的经典应用是下一个更大元素给定一个数组找出每个元素右边第一个比它大的元素。暴力解法是两层循环O(n²)。用单调栈可以做到O(n)。def next_greater_element(nums): result [-1] * len(nums) stack [] # 存储索引对应值单调递减 for i in range(len(nums)): while stack and nums[stack[-1]] nums[i]: idx stack.pop() result[idx] nums[i] stack.append(i) return result思路是维护一个单调递减的栈。当遇到一个比栈顶元素大的新元素时说明栈顶元素的下一个更大元素就是当前元素弹出并记录。每个元素最多入栈一次、出栈一次所以总时间复杂度是O(n)。单调队列的经典应用是滑动窗口最大值给定一个数组和窗口大小k找出每个窗口中的最大值。用单调队列可以在O(n)时间内解决。from collections import deque def max_sliding_window(nums, k): result [] dq deque() # 存储索引对应值单调递减 for i in range(len(nums)): # 移除超出窗口范围的索引 while dq and dq[0] i - k: dq.popleft() # 维护单调递减 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 窗口形成后开始记录结果 if i k - 1: result.append(nums[dq[0]]) return result单调队列的关键在于队列头部始终是当前窗口的最大值。每次新元素入队前把队列尾部所有比它小的元素弹出保证队列单调递减。同时队列头部的索引如果超出窗口范围也要弹出。这两个操作保证了队列中存储的始终是当前窗口内的有效候选最大值。5. 栈和队列的组合变形与高频面试题5.1 用两个栈实现队列这是最经典的组合题。思路是用一个栈in_stack负责入队另一个栈out_stack负责出队。入队时直接压入in_stack出队时如果out_stack为空就把in_stack的所有元素依次弹出并压入out_stack这样顺序就反过来了再从out_stack弹出就是正确的出队顺序。class QueueWithTwoStacks: def __init__(self): self._in [] self._out [] def enqueue(self, value): self._in.append(value) def dequeue(self): if not self._out: while self._in: self._out.append(self._in.pop()) if not self._out: raise IndexError(dequeue from empty queue) return self._out.pop() def is_empty(self): return not self._in and not self._out这里有一个重要的优化点只有当out_stack为空时才把in_stack的元素倒过去。如果每次出队都倒一次虽然结果正确但均摊时间复杂度会变差。按照只在out为空时倒的策略每个元素最多被倒入out一次均摊时间复杂度是O(1)。5.2 用两个队列实现栈反过来用两个队列实现栈稍微绕一点。思路是入栈时把元素放入非空的那个队列出栈时把非空队列中除最后一个元素外的所有元素移到另一个队列然后弹出最后一个元素。class StackWithTwoQueues: def __init__(self): self._q1 deque() self._q2 deque() def push(self, value): # 放入非空队列如果都空就放q1 if self._q1: self._q1.append(value) else: self._q2.append(value) def pop(self): # 找到非空队列和空队列 if self._q1: non_empty, empty self._q1, self._q2 elif self._q2: non_empty, empty self._q2, self._q1 else: raise IndexError(pop from empty stack) # 把非空队列的前n-1个元素移到空队列 while len(non_empty) 1: empty.append(non_empty.popleft()) return non_empty.popleft()用两个队列实现栈的pop操作时间复杂度是O(n)因为需要移动n-1个元素。这是它和两个栈实现队列最大的区别——后者均摊O(1)前者最坏O(n)。面试中如果被问到要能说清楚这个差异。5.3 最小栈的设计最小栈要求在O(1)时间内获取栈中的最小元素。核心思路是用一个辅助栈同步记录当前最小值。class MinStack: def __init__(self): self._data [] self._min_stack [] # 辅助栈栈顶是当前最小值 def push(self, value): self._data.append(value) if not self._min_stack or value self._min_stack[-1]: self._min_stack.append(value) def pop(self): if not self._data: raise IndexError(pop from empty stack) value self._data.pop() if value self._min_stack[-1]: self._min_stack.pop() return value def get_min(self): if not self._min_stack: raise IndexError(stack is empty) return self._min_stack[-1]这里有一个细节push时判断条件是value self._min_stack[-1]而不是。为什么要用因为如果压入了多个相同的最小值弹出时只弹出一个辅助栈里还需要保留另一个。如果用重复的最小值就不会被记录弹出时辅助栈会提前变空导致错误。6. 复习中常见的坑与排查技巧6.1 栈和队列的边界条件速查表下面这张表整理了栈和队列操作中最容易出错的边界条件建议复习时对照检查。操作常见错误正确做法栈的pop空栈时直接pop先检查is_empty()或捕获异常栈的peek空栈时访问栈顶先检查is_empty()循环队列的enqueue队满时继续入队检查size capacity循环队列的dequeue队空时继续出队检查size 0循环队列的索引忘记取模导致越界所有索引移动都加% capacity链表队列的dequeue队列变空后tail未置空出队后若head为Nonetail也置None单调栈忘记处理栈中剩余元素遍历结束后处理栈中剩余元素单调队列忘记移除过期索引每次循环先检查队头是否过期6.2 调试栈和队列问题的实用技巧调试栈和队列相关代码时最有效的方法是在每次操作后打印当前状态。但直接打印整个栈或队列可能不够直观我习惯用以下方式对于栈打印从栈底到栈顶的完整内容这样能清楚看到元素的顺序。对于队列打印从队头到队尾的内容。对于循环队列额外打印front和size的值这样能验证索引计算是否正确。另一个技巧是用小规模数据手动模拟。比如循环队列用容量为3的数组手动模拟入队、出队、再入队的过程把每一步的front、rear、size都写出来。这个过程看起来笨但能帮你彻底理解循环队列的索引变化规律。我当年就是靠手动画图才真正搞懂循环队列的。提示如果一道题你写了很久还是不对先别急着改代码。拿一张纸用3到5个元素手动模拟一遍你的算法把每一步的栈或队列状态画出来。大多数时候你会在模拟过程中发现逻辑漏洞。6.3 选择栈还是队列的判断依据复习到后期最重要的能力不是写出栈或队列的代码而是看到一道题能快速判断该用栈还是队列。我总结了一个简单的判断流程。如果问题涉及最近的匹配的嵌套的回退的撤销的优先考虑栈。比如括号匹配、函数调用、浏览器后退、编辑器撤销。如果问题涉及按层按顺序最短路径广度优先排队优先考虑队列。比如层序遍历、BFS、任务调度、消息队列。如果问题涉及滑动窗口区间最值下一个更大/更小考虑单调栈或单调队列。如果问题涉及用A实现B的组合考虑两个栈或两个队列的配合。这个判断流程不是绝对的但能覆盖大部分常见题型。真正做题时还需要结合具体条件灵活调整。7. 从复习到实战的过渡建议7.1 刷题顺序与难度递进复习完基础后建议按照以下顺序刷题难度从低到高递进。第一阶段巩固基础操作。做有效的括号、用栈实现队列、用队列实现栈、最小栈这几道题。目标是能不看题解独立写出正确代码并且处理好所有边界条件。第二阶段掌握典型应用。做逆波兰表达式求值、二叉树的层序遍历、二叉树的最大深度、岛屿数量这几道题。目标是能识别出题目背后的栈或队列模式。第三阶段攻克进阶变形。做每日温度单调栈、滑动窗口最大值单调队列、字符串解码栈的嵌套应用这几道题。目标是能灵活组合栈和队列解决复杂问题。每个阶段不要贪多做透比做多重要。一道题做完后想想能不能用另一种方法解能不能优化时间复杂度能不能处理更大的数据规模。7.2 复习笔记的整理方法我建议用问题模式而不是题目编号来整理笔记。比如不要写第20题有效的括号而是写括号匹配模式遇到左括号入栈遇到右括号检查栈顶最后检查栈空。这样整理的好处是当你遇到新题时能快速匹配到已有的模式而不是从零开始想。每个模式下面记录三样东西触发条件什么特征提示用这个模式、核心步骤算法的关键步骤、易错点边界条件和常见bug。这三样东西才是复习的真正产出比代码本身更有价值。7.3 面试中的表达技巧面试中被问到栈和队列相关问题时不要上来就写代码。先用一两句话说明你的思路比如这道题我打算用单调栈来解决因为需要找下一个更大元素。然后说明时间复杂度和空间复杂度。最后再写代码。写代码时边写边解释关键步骤特别是边界处理。比如这里我先检查栈是否为空避免空栈访问。这样即使代码有小bug面试官也能看到你的思路是清晰的。如果卡住了不要沉默。可以说我先用一个小例子模拟一下然后手动走一遍算法。这个过程本身就能帮你发现问题和理清思路。栈和队列的复习说到底就是把这两个结构从知道变成会用。定义五分钟就能背下来但真正的功夫在识别问题模式、处理边界条件、组合变形这几个方面。我自己的经验是复习完这一章后不要急着往下翻找十道相关的题做一遍做完再回头看看这篇内容会有不一样的体会。后面遇到树、图、动态规划的时候你会发现栈和队列的影子无处不在那时候再回来复习一遍理解又会深一层。