第 7 课 - 双端队列 (Double-Ended Queue, Deque)
所属模块：基础概念
难度：beginner
标签：deque, double-ended, sliding-window
上一课：队列
下一课：哈希表
学习目标
通过本课的学习，你将能够：
- 理解概念：清晰地阐述双端队列（Deque）是什么，以及它与普通队列和栈的主要区别。
- 掌握基本操作：熟练使用双端队列的核心方法，实现从两端进行插入和删除元素。
- 认识灵活性：理解双端队列如何模拟栈和队列的两种行为。
- 应用场景：能够识别并描述一个适合使用双端队列的经典算法问题（如滑动窗口最大值）。
核心概念
想象一下你在一个银行大厅办理业务。普通的队列就像只有一侧有窗口（队首）可以办理业务，所有人必须按顺序排在队尾等待。
而双端队列（Deque） 则像是一个两侧都有开放窗口的柜台。人们不仅可以在队尾排队，也可以从队伍的前端插入（比如有VIP客户来了），甚至队伍前端的人也可以快速办完离开，而队尾的人也可能因为某种原因需要退出。总之，两端都是“活动”的。
用更技术的语言来说，双端队列是一种允许在头部（前端）和尾部（后端） 都能进行 插入 和 删除 操作的线性数据结构。这使得它极其灵活：
- 如果只在一端进行插入和删除，它就表现得像一个栈（后进先出）。
- 如果只在队尾插入，队首删除，它就表现得像一个普通的队列（先进先出）。
在 Python 中，标准库 collections 提供了高效的 deque 类。它内部通过一个双向链表实现，因此两端操作的时间复杂度通常为 O(1)，非常高效。
代码示例
首先，我们需要从 collections 模块导入 deque。
from collections import deque
# 1. 创建一个双端队列
dq = deque() # 创建一个空的双端队列
print(f"初始状态: {dq}")
# 也可以用一个列表初始化
dq_from_list = deque([1, 2, 3])
print(f"从列表初始化: {dq_from_list}")
# 2. 核心操作：两端插入和删除
# 向右端（队尾）添加元素
dq.append('A') # 在队尾添加
dq.append('B')
print(f"append('A') 和 append('B') 后: {dq}")
# 向左端（队首）添加元素
dq.appendleft('X') # 在队首添加
print(f"appendleft('X') 后: {dq}")
# 从右端（队尾）删除元素
right_item = dq.pop() # 弹出并返回队尾元素
print(f"pop() 弹出了: '{right_item}'，剩余: {dq}")
# 从左端（队首）删除元素
left_item = dq.popleft() # 弹出并返回队首元素
print(f"popleft() 弹出了: '{left_item}'，剩余: {dq}")
# 3. 访问两端元素（不删除）
print(f"队首元素 (dq[0]): {dq[0]}")
print(f"队尾元素 (dq[-1]): {dq[-1]}")
# 4. 模拟栈 (LIFO) - 只使用一端 (例如右端)
stack = deque()
stack.append(1) # push
stack.append(2)
stack.append(3)
print(f"\n用双端队列模拟栈: {stack}")
last_item = stack.pop() # pop
print(f"栈弹出元素: {last_item}，栈剩余: {stack}")
# 5. 经典应用示例：滑动窗口最大值 (概念演示)
# 问题：给定一个数组和窗口大小k，找出每个滑动窗口中的最大值。
# 双端队列可以高效维护窗口内可能成为最大值的元素索引。
def sliding_window_max_simple(nums, k):
"""用双端队列实现滑动窗口最大值（简化理解版）"""
if not nums or k <= 0:
return []
dq = deque() # 存储可能成为最大值的**索引**
result = []
for i, num in enumerate(nums):
# 1. 移除滑出窗口的元素索引（从队首检查）
while dq and dq[0] < i - k + 1:
dq.popleft()
# 2. 维护队列单调性：如果新元素比队尾元素大，队尾元素永不可能成为窗口最大值，弹出。
while dq and nums[dq[-1]] < num:
dq.pop()
# 3. 将当前元素索引加入队列
dq.append(i)
# 4. 当窗口完全形成后，记录最大值（队首对应的元素）
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 测试滑动窗口最大值
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
max_values = sliding_window_max_simple(nums, k)
print(f"\n滑动窗口最大值示例:")
print(f"输入数组: {nums}, 窗口大小k={k}")
print(f"输出: {max_values}") # 应为 [3, 3, 5, 5, 6, 7]
输出结果：
初始状态: deque([])
从列表初始化: deque([1, 2, 3])
append('A') 和 append('B') 后: deque(['A', 'B'])
appendleft('X') 后: deque(['X', 'A', 'B'])
pop() 弹出了: 'B'，剩余: deque(['X', 'A'])
popleft() 弹出了: 'X'，剩余: deque(['A'])
队首元素 (dq[0]): A
队尾元素 (dq[-1]): A
用双端队列模拟栈: deque([1, 2, 3])
栈弹出元素: 3，栈剩余: deque([1, 2])
滑动窗口最大值示例:
输入数组: [1, 3, -1, -3, 5, 3, 6, 7], 窗口大小k=3
输出: [3, 3, 5, 5, 6, 7]
实践练习
练习 1：基础操作
创建一个双端队列，依次执行以下操作，并打印每一步后的状态：
- 初始化为空。
- 从右端依次添加数字
10, 20, 30。 - 从左端添加数字
5。 - 从右端删除一个元素。
- 从左端删除一个元素。
预期输出示例：
初始化后: deque([])
append(10,20,30)后: deque([10, 20, 30])
appendleft(5)后: deque([5, 10, 20, 30])
pop()后: deque([5, 10, 20])
popleft()后: deque([10, 20])
练习 2：历史记录模拟
使用双端队列模拟一个浏览器历史记录或文本编辑器的“撤销”功能。要求：
- 实现
add_item(item)函数：向历史记录的“末尾”（当前状态）添加一条记录。 - 实现
undo()函数：撤销最近的一次操作（即从末尾移除）。 - 扩展：限制历史记录最多保存 5 条。当添加第 6 条时，自动丢弃最早的一条。
练习 3：简单工作调度器
用双端队列模拟一个简单的工作任务队列。假设你有两个操作：
add_job(job)：普通任务，添加到队列末尾。add_priority_job(job)：紧急任务，添加到队列开头，优先执行。process_job()：从队列开头取出一个任务执行。
实现这个调度器，并测试添加几个普通和紧急任务后，处理任务的顺序是否符合预期。
常见错误
-
方法名称混淆：初学者最容易搞错的是
append/appendleft和pop/popleft的方向。append：添加到右端（队尾）。记住“Append”这个词，通常联想为在列表末尾添加。appendleft：添加到左端（队首）。pop：移除**右端（队尾）**元素。这与列表的pop()默认行为一致。popleft：移除**左端（队首）**元素。- 记忆口诀：带
left的在左（队首）操作，不带的在右（队尾）操作。
-
在空双端队列上执行删除操作：对一个空的
deque调用pop()或popleft()会抛出IndexError。在进行删除操作前，最好先用len(dq)或直接if dq:检查队列是否为空。 -
误以为双端队列是“万能”的：虽然灵活，但在某些场景下，专用的数据结构可能更优。例如，如果只需要栈或队列，使用对应的结构会使代码意图更清晰。
小结
本节课我们学习了强大的双端队列（Deque）：
- 是什么：一种允许在头部和尾部进行高效（O(1)）插入和删除操作的线性数据结构。
- 核心操作：
append（右端加）、appendleft（左端加）、pop（右端删）、popleft（左端删）。 - 灵活性：它可以轻松模拟栈（只用
append和pop）和队列（只用append和popleft）。 - 应用关键：在需要从两端维护数据序列的问题中非常有用，例如本课示例的滑动窗口最大值算法。
掌握双端队列，为你解决更复杂的算法问题（如单调队列、BFS等）增添了一个重要工具。下一课，我们将进入 哈希表 的世界！