栈、队列与堆
栈（Stack）和队列（Queue）是最基础的线性数据结构，而堆（Heap）是实现优先队列的核心。这三者在面试中都有大量经典题目。
一、栈（Stack）
特性
后进先出（LIFO, Last In First Out）
push(1) push(2) push(3)
↓
[1, 2, 3] ← top
pop() → 3
pop() → 2
基础实现
class Stack:
def __init__(self):
self.items = []
def push(self, x):
self.items.append(x)
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
return self.items.pop()
def peek(self):
return self.items[-1] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
经典应用：括号匹配
def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
单调栈（Monotonic Stack）
维护栈内元素单调递增或递减，用于解决「下一个更大/更小元素」问题。
def next_greater_elements(nums):
"""找到每个元素右边第一个更大的元素"""
n = len(nums)
result = [-1] * n
stack = [] # 递减栈，存索引
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
扩展：循环数组
def next_greater_elements_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n): # 模拟循环
idx = i % n
while stack and nums[idx] > nums[stack[-1]]:
result[stack.pop()] = nums[idx]
if i < n:
stack.append(idx)
return result
二、队列（Queue）
特性
先进先出（FIFO, First In First Out）
基础实现
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, x):
self.items.append(x)
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
return self.items.popleft()
def front(self):
return self.items[0] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
双端队列（Deque）
两端都可以插入删除，是更灵活的数据结构。
from collections import deque
d = deque()
d.append(1) # 右侧入队
d.appendleft(2) # 左侧入队
d.pop() # 右侧出队
d.popleft() # 左侧出队
应用：滑动窗口最大值（LeetCode 239）
def max_sliding_window(nums, k):
result = []
dq = deque() # 存索引，维护递减
for i, num in enumerate(nums):
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
用栈实现队列 / 用队列实现栈
面试常考的设计题，考察对两种结构的理解。
# 用两个栈实现队列
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x):
self.stack_in.append(x)
def pop(self):
self.peek()
return self.stack_out.pop()
def peek(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1]
def empty(self):
return not self.stack_in and not self.stack_out
三、堆（Heap）
二叉堆性质
- 完全二叉树（适合数组存储）
- 大根堆：父节点 ≥ 子节点
- 小根堆：父节点 ≤ 子节点
数组表示
10 index 0
/ \
8 9 index 1, 2
/ \ / \
5 6 7 4 index 3, 4, 5, 6
- 父节点 i 的左子节点：2i + 1
- 父节点 i 的右子节点：2i + 2
- 子节点 i 的父节点：(i - 1) // 2
堆化（Heapify）
def heapify_down(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify_down(arr, n, largest)
def build_heap(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify_down(arr, n, i)
建堆复杂度：O(n)（不是 O(n log n)，可用等比数列证明）
堆排序
def heap_sort(arr):
n = len(arr)
build_heap(arr)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 最大值放到末尾
heapify_down(arr, i, 0)
return arr
复杂度：时间 O(n log n)，空间 O(1)（原地排序）。
Top K 问题
思路：维护一个大小为 K 的小根堆，遍历数组。
import heapq
def top_k_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap
复杂度：O(n log k)，当 k « n 时优于 O(n log n) 的全排序。
变体：
- 第 K 大：维护小根堆（堆顶是第 K 大）
- 第 K 小：维护大根堆（Python 用负数模拟）
- Top K 频率：哈希表计数 + 堆
四、经典面试题
| 题号 | 题目 | 考点 | 难度 |
|---|---|---|---|
| LeetCode 20 | 有效的括号 | 栈基础 | Easy |
| LeetCode 155 | 最小栈 | 辅助栈 | Medium |
| LeetCode 739 | 每日温度 | 单调栈 | Medium |
| LeetCode 232 | 用栈实现队列 | 设计 | Easy |
| LeetCode 225 | 用队列实现栈 | 设计 | Easy |
| LeetCode 239 | 滑动窗口最大值 | 单调队列 | Hard |
| LeetCode 215 | 数组中的第K个最大元素 | 快速选择/堆 | Medium |
| LeetCode 347 | 前 K 个高频元素 | 哈希 + 堆 | Medium |
| LeetCode 295 | 数据流的中位数 | 双堆 | Hard |
五、面试常见问题
Q: 栈和队列的本质区别是什么？
- 栈：LIFO，适合「回溯」「撤销」「表达式求值」
- 队列：FIFO，适合「BFS」「缓冲」「任务调度」
Q: 为什么说堆适合找 Top K？
堆可以在 O(log k) 时间内维护一个固定大小的有序集合，总复杂度 O(n log k)。当 k 很小时，远优于排序的 O(n log n)。
Q: 实际工程中什么时候用堆？
- 优先队列（任务调度）
- 合并 K 个有序数组
- 滑动窗口统计
- 流式数据的 Top K（无法全量排序）
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。