引言
deque（双端队列）是Python中collections模块提供的一个高效数据结构，支持从两端快速添加和删除元素。它非常适合用于实现队列、栈、滑动窗口等场景。本文将详细介绍deque的关键用法和特性，并通过8个丰富的案例帮助读者掌握其应用。
deque-关键用法及特性
| 特性/方法 | 描述 |
|---|---|
| 双端操作 | 支持从队列的头部和尾部高效添加和删除元素。 |
| 线程安全 | deque是线程安全的，适合多线程环境。 |
| 固定大小 | 可以设置最大长度，当队列满时自动丢弃另一端的数据。 |
| 高效性能 | 从两端添加和删除元素的时间复杂度为O(1)。 |
| 初始化 | 使用deque(iterable, maxlen=None)创建。 |
append(x) | 在队列尾部添加元素。 |
appendleft(x) | 在队列头部添加元素。 |
pop() | 从队列尾部移除并返回元素。 |
popleft() | 从队列头部移除并返回元素。 |
rotate(n) | 将队列旋转n步（正数向右，负数向左）。 |
maxlen | 返回队列的最大长度（如果未设置，返回None）。 |
1. deque的概念
deque（双端队列）是collections模块中的一个高效数据结构，支持从两端快速添加和删除元素。它的主要特点是：
- 双端操作：支持从头部和尾部高效添加和删除元素。
- 线程安全：适合多线程环境。
- 固定大小：可以设置最大长度，当队列满时自动丢弃另一端的数据。
- 高效性能：从两端添加和删除元素的时间复杂度为O(1)。
2. deque的用法
2.1 创建deque
from collections import deque# 创建一个空的双端队列
d = deque()
print(d) # 输出: deque([])# 从列表创建双端队列
d = deque([1, 2, 3])
print(d) # 输出: deque([1, 2, 3])
2.2 添加元素
# 在尾部添加元素
d.append(4)
print(d) # 输出: deque([1, 2, 3, 4])# 在头部添加元素
d.appendleft(0)
print(d) # 输出: deque([0, 1, 2, 3, 4])
2.3 删除元素
# 从尾部移除元素
print(d.pop()) # 输出: 4
print(d) # 输出: deque([0, 1, 2, 3])# 从头部移除元素
print(d.popleft()) # 输出: 0
print(d) # 输出: deque([1, 2, 3])
3. deque的常见方法
3.1 rotate(n)：旋转队列
# 向右旋转1步
d.rotate(1)
print(d) # 输出: deque([3, 1, 2])# 向左旋转1步
d.rotate(-1)
print(d) # 输出: deque([1, 2, 3])
3.2 maxlen：设置最大长度
# 创建一个最大长度为3的双端队列
d = deque([1, 2, 3], maxlen=3)
d.append(4) # 队列满时，头部元素被丢弃
print(d) # 输出: deque([2, 3, 4], maxlen=3)
4. deque的8个应用案例
案例1：实现队列（FIFO）
# 使用deque实现队列
queue = deque()
queue.append(1) # 入队
queue.append(2)
print(queue.popleft()) # 出队，输出: 1
案例2：实现栈（LIFO）
# 使用deque实现栈
stack = deque()
stack.append(1) # 入栈
stack.append(2)
print(stack.pop()) # 出栈，输出: 2
案例3：滑动窗口最大值
# 使用deque实现滑动窗口最大值
def max_sliding_window(nums, k):d = deque()result = []for i, num in enumerate(nums):while d and nums[d[-1]] < num:d.pop()d.append(i)if d[0] == i - k:d.popleft()if i >= k - 1:result.append(nums[d[0]])return resultnums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3)) # 输出: [3, 3, 5, 5, 6, 7]
案例4：回文检查
# 使用deque检查字符串是否是回文
def is_palindrome(s):d = deque(s.lower().replace(" ", ""))while len(d) > 1:if d.popleft() != d.pop():return Falsereturn Trueprint(is_palindrome("A man a plan a canal Panama")) # 输出: True
案例5：任务调度
# 使用deque实现任务调度
tasks = deque(["task1", "task2", "task3"])
while tasks:current_task = tasks.popleft()print(f"正在执行: {current_task}")
案例6：多线程任务队列
# 使用deque实现多线程任务队列
import threadingdef worker(task_queue):while task_queue:task = task_queue.popleft()print(f"处理任务: {task}")task_queue = deque(["task1", "task2", "task3"])
threads = [threading.Thread(target=worker, args=(task_queue,)) for _ in range(2)]
for t in threads:t.start()
for t in threads:t.join()
案例7：固定大小的历史记录
# 使用deque实现固定大小的历史记录
history = deque(maxlen=3)
history.append("page1")
history.append("page2")
history.append("page3")
history.append("page4") # 超出最大长度，丢弃最早的元素
print(history) # 输出: deque(['page2', 'page3', 'page4'], maxlen=3)
案例8：旋转数组
# 使用deque实现数组旋转
def rotate_array(nums, k):d = deque(nums)d.rotate(k)return list(d)nums = [1, 2, 3, 4, 5]
print(rotate_array(nums, 2)) # 输出: [4, 5, 1, 2, 3]
总结
deque是Python中一个非常高效的数据结构，适合用于实现队列、栈、滑动窗口等场景。通过本文的详细讲解和8个实际案例，读者可以快速掌握deque的使用方法，并在实际项目中灵活应用。