deque 是 Python 的 collections 模块提供的一种 双端队列 数据结构，支持从队列的两端快速添加和删除元素，时间复杂度为 (O(1))。与列表相比，它在高效的双端操作中有明显优势。
1. 导入 deque
from collections import deque
2. 初始化 deque
创建空队列
dq = deque()
print(dq) # deque([])
从可迭代对象初始化
dq = deque([1, 2, 3, 4])
print(dq) # deque([1, 2, 3, 4])
设置最大长度
dq = deque([1, 2, 3], maxlen=5)
print(dq) # deque([1, 2, 3], maxlen=5)
maxlen限制队列长度，超出后从另一端自动移除元素。
3. 主要方法
（1）添加元素
append(item)：在右端添加元素。appendleft(item)：在左端添加元素。
dq = deque([1, 2, 3])
dq.append(4)
dq.appendleft(0)
print(dq) # deque([0, 1, 2, 3, 4])
（2）删除元素
pop()：移除并返回右端元素。popleft()：移除并返回左端元素。
dq = deque([1, 2, 3, 4])
print(dq.pop()) # 4
print(dq.popleft()) # 1
print(dq) # deque([2, 3])
（3）扩展队列
extend(iterable)：在右端扩展队列。extendleft(iterable)：在左端扩展队列（反向添加）。
dq = deque([1, 2])
dq.extend([3, 4])
dq.extendleft([0, -1])
print(dq) # deque([-1, 0, 1, 2, 3, 4])
（4）旋转队列
rotate(n)：将队列右移 (n) 步（负值为左移）。
dq = deque([1, 2, 3, 4])
dq.rotate(2)
print(dq) # deque([3, 4, 1, 2])
dq.rotate(-1)
print(dq) # deque([4, 1, 2, 3])
（5）访问队列
- 索引访问：可直接用索引访问队列中的元素。
dq = deque([1, 2, 3])
print(dq[0]) # 1
print(dq[-1]) # 3
（6）清空队列
clear()：清空队列。
dq = deque([1, 2, 3])
dq.clear()
print(dq) # deque([])
（7）队列长度
len(deque)：获取队列长度。
dq = deque([1, 2, 3])
print(len(dq)) # 3
4. maxlen 限制
maxlen 是 deque 的特殊功能，限制队列长度。如果长度超过 maxlen，新添加的元素会自动移除另一端的元素。
dq = deque([1, 2, 3], maxlen=3)
dq.append(4) # 超出长度限制，左端元素被移除
print(dq) # deque([2, 3, 4])
dq.appendleft(0)
print(dq) # deque([0, 2, 3])
5. 时间复杂度
- 添加和删除（两端）：(O(1))
- 随机访问：(O(n))（不如列表高效）
- 遍历：(O(n))
6. 常见用法场景
队列
用于先进先出的队列：
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
print(dq.popleft()) # 1
print(dq.popleft()) # 2
滑动窗口
用 deque 实现固定大小的滑动窗口：
dq = deque(maxlen=3)
for i in range(1, 6):
dq.append(i)
print(list(dq)) # 窗口内的元素
# 输出：
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4]
# [3, 4, 5]
回文检测
检查字符串是否为回文：
def is_palindrome(s: str) -> bool:
dq = deque(s)
while len(dq) > 1:
if dq.popleft() != dq.pop():
return False
return True
print(is_palindrome("radar")) # True
print(is_palindrome("hello")) # False
deque 的灵活性和高效性能，使它在实现队列、双端队列、滑动窗口等场景中非常常用。