双端队列：左右通吃（Deque）

---

元数据卡

属性	值
章节编号	Vol 2 · 第3章 · 双端队列
难度等级	（入门加固）
前置知识	队列（第3章）
核心技能	头尾 O(1) 操作、collections.deque、滑动窗口
关键字	Deque Double-Ended Queue collections.deque

---

你的进度

独木舟漂到一个三岔河口。左边有鱼，右边有果。你正犹豫先拿哪边，发现河马大爷左右都能张嘴——双端队列就像河马的嘴：两边都能加，两边都能取。

普通的队列只能尾部入队、头部出队。但有些场景——比如撤销/重做、滑动窗口、任务双端调度——你需要在两边操作。

Python 标准库的 collections.deque 就是为此而生：

Python

from collections import deque

# Deque —— 两边都能加，两边都能取
river = deque()

# 右侧（尾部）操作 —— 和普通队列一样
river.append("🐟 鱼")   # 右边进
river.append("🦐 虾")

# 左侧（头部）操作 —— 普通队列做不到
river.appendleft("🍎 苹果")   # 左边进
river.appendleft("🍌 香蕉")

print("当前队列:", list(river))

# 两边都能取
print("右边出:", river.pop())      # 虾
print("左边出:", river.popleft())  # 香蕉

Output

当前队列: ['🍌 香蕉', '🍎 苹果', '🐟 鱼', '🦐 虾']
右边出: 🦐 虾
左边出: 🍌 香蕉

Java 视角：ArrayDeque<E> 就是 Java 的 deque 实现，做队列用 offer/poll，做栈用 push/pop，全在一个类里。

C++ 视角：std::deque<T> 是分段连续存储——对标 Python 的 collections.deque，但底层实现不同。

---

对比三兄弟

你把三种容器摆在一起看：

操作	栈（Stack）	队列（Queue）	双端队列（Deque）
左侧插入	❌	❌	✅ appendleft(x)
右侧插入	✅ append(x)	✅ append(x)	✅ append(x)
左侧取出	❌	✅ popleft()	✅ popleft()
右侧取出	✅ pop()	❌	✅ pop()
核心特性	后进先出	先进先出	左右通吃
Python 实现	list	deque 或自定义循环队列	deque

简单记：栈只用一头，队列用两头但各只进/出一边，deque 两头都能进也能出。

---

常见陷阱

拆解 #1：什么时候该用 deque 而不是 list？

很多场景里 list 能凑合，但一旦你需要在左侧操作，就应该换成 deque：

• 用 list.insert(0, x) 插入头部 → O(n) → 用 deque.appendleft(x) → O(1)
• 用 list.pop(0) 弹出头部 → O(n) → 用 deque.popleft() → O(1)

经验法则： 如果代码里出现 list.pop(0) 或 list.insert(0, ...)，立马换成 deque。

---

进阶一瞥：滑动窗口最大值

你在森林望远镜里一次只能看到连续 k 棵树。每移动一格，你要报告当前窗口里最高的树——滑动窗口最大值是 monotonic deque 的经典应用。

思路： 维护一个单调递减的 deque（存索引），队首永远是当前窗口的最大值。

本节属于进阶内容，主线先掌握 deque 的基本操作即可。

---

验收标准

• [ ] 能区分栈、队列、deque 三者的头尾操作差异
• [ ] 知道 Python 从哪里导入 deque
• [ ] 在什么场景下应该用 deque 代替 list
• [ ] 知道头尾各操作的时间复杂度（都是 O(1)）

---

常见卡点

卡点	破法
deque 和 list 分不清	只在需要 头尾操作 时用 deque；随机访问用 list
Java 里用什么	ArrayDeque 既是栈也是队列也是 deque，一个类搞定一切
C++ deque 是分段存储	对使用者透明，你只需要知道它头尾 O(1) 就行
滑动窗口左边不及时 pop	检查索引是否滑出窗口，别检查值——值可能重复

---

旅人笔记

1. 双端队列 = 左右通吃。头尾操作全是 O(1)。
2. Python 用 collections.deque，走遍天下都不怕。
3. 栈能做到的，deque 都能做；队列能做到的，deque 也都能做。
4. 看到 list.pop(0) 就条件反射换成 deque。

三种容器都塞进背包了。前面就是哈希森林，那里的树靠哈希函数导航——每个元素都有一个"钥匙孔"。

---

→ 下一站预告

第4章：哈希表——"把 O(n) 的查找变成 O(1)，靠的是魔法还是数学？你马上就会知道。顺便，你得先想清楚：如果两个东西算出的钥匙一样怎么办？"

回看这一章的前两节：

• 栈——后进先出
• 队列——先进先出

---

代码仓库位置： vol-02-dsa/examples/ch03/ 下有此章完整示例代码