📑 本页目录（点开跳转）
03 · 栈、队列和窗口：谁应该先出来
⏱ 10 分钟 ｜ 两个栈实现队列、min 栈、滑动窗口最大值
🎯 一句话
这类题先不写代码，先问：我需要最早的、最新的，还是目前最大的那个？
🧩 题 1：用两个栈实现队列
一个栈负责“新来的放进去”，另一个负责“最早来的拿出来”。只有输出栈空了，才把输入栈整批倒过去。
class TwoStackQueue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, value):
self.inbox.append(value)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
if not self.outbox:
raise IndexError("queue is empty")
return self.outbox.pop()
queue = TwoStackQueue()
for value in [1, 2, 3]:
queue.push(value)
assert [queue.pop(), queue.pop(), queue.pop()] == [1, 2, 3]
不变量：outbox 顶部永远是当前最早进入、还没出去的元素。
🧩 题 2：包含 min 函数的栈
别在每次 min() 时把栈扫一遍。再放一个 mins 栈：每一层都记“走到这里为止的最小值”。
class MinStack:
def __init__(self):
self.data, self.mins = [], []
def push(self, value):
self.data.append(value)
self.mins.append(value if not self.mins else min(value, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.data.pop()
def get_min(self):
return self.mins[-1]
stack = MinStack()
for value in [3, 1, 2]:
stack.push(value)
assert stack.get_min() == 1
stack.pop()
stack.pop()
assert stack.get_min() == 3
🧩 题 3：滑动窗口的最大值
窗口向右移动时，过期下标从队首丢掉；新值进来前，把比它小的候选从队尾丢掉。队列里只留可能成为最大值的人。
from collections import deque
def max_sliding_window(nums, k):
queue, answer = deque(), [] # queue 存下标，值从大到小
for right, value in enumerate(nums):
while queue and queue[0] <= right - k:
queue.popleft()
while queue and nums[queue[-1]] <= value:
queue.pop()
queue.append(right)
if right >= k - 1:
answer.append(nums[queue[0]])
return answer
assert max_sliding_window([2, 3, 4, 2, 6, 2, 5, 1], 3) == [4, 4, 6, 6, 6, 5]
⭐ 队列存下标不是细节：这样才能知道队首是否已经离开窗口。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 05 · 状态空间与搜索框架 | ⭐ 「谁应该先出来」正是那一章的全部问题：BFS、DFS、迭代加深、一致代价、A* 共用一个骨架，差别只在待展开集合用什么容器 |
🛑 可以停在这里
栈管“最近”，队列管“最早”，单调队列管“窗口里还可能赢的人”。
✅ 检查点
滑动窗口最大值为什么能丢掉比新值小的队尾元素？
👀 看答案
新值更靠右、又至少一样大；旧的小值会更早过期，并且永远不可能再成为最大值。
⚡ 走神救援
- 两栈队列：输入栈收新元素，输出栈只在空时整批倒。
- min 栈：每层同步保存当时最小值。
- 窗口：过期从左丢，弱者从右丢，队首就是答案。