双端队列（Deque）是一种具有队列和栈性质的数据结构，支持在两端高效添加和移除元素。Python的collections模块提供了deque实现，它是线程安全的，且针对快速插入和删除进行了优化。

什么是双端队列？

双端队列（Deque，全名double-ended queue）是一种允许在队列的前端（front）和后端（rear）进行插入和删除操作的线性数据结构。

A
B
C
D
E

创建双端队列

使用collections.deque创建双端队列：

from collections import deque

# 创建空双端队列
d = deque()

# 从可迭代对象创建双端队列
d = deque(['apple', 'banana', 'cherry'])

# 指定最大长度（可选）
d = deque(maxlen=5)  # 最多容纳5个元素

基本操作方法

双端队列支持在两端高效添加和删除元素：

方法 描述 时间复杂度
append(x) 在右端添加元素x O(1)
appendleft(x) 在左端添加元素x O(1)
pop() 移除并返回右端元素 O(1)
popleft() 移除并返回左端元素 O(1)
extend(iterable) 在右端扩展多个元素 O(k)
extendleft(iterable) 在左端扩展多个元素 O(k)
rotate(n) 向右旋转n步（负值向左） O(k)
clear() 清空队列 O(n)

使用示例

from collections import deque

# 创建双端队列
d = deque(['b', 'c', 'd'])
print(d)  # deque(['b', 'c', 'd'])

# 添加元素
d.append('e')       # 右端添加
d.appendleft('a')   # 左端添加
print(d)  # deque(['a', 'b', 'c', 'd', 'e'])

# 移除元素
right = d.pop()      # 移除右端元素
left = d.popleft()   # 移除左端元素
print(f"Removed: {left}, {right}")  # Removed: a, e
print(d)  # deque(['b', 'c', 'd'])

# 旋转操作
d.rotate(1)   # 向右旋转1步
print(d)  # deque(['d', 'b', 'c'])

d.rotate(-2)  # 向左旋转2步
print(d)  # deque(['c', 'd', 'b'])

实际应用场景

1

实现队列和栈

使用双端队列可以轻松实现标准队列（FIFO）和栈（LIFO）结构：

# 队列实现 (FIFO)
queue = deque()
queue.append('a')  # 入队
queue.append('b')
item = queue.popleft()  # 出队
print(item)  # 'a'

# 栈实现 (LIFO)
stack = deque()
stack.append('a')  # 压栈
stack.append('b')
item = stack.pop()  # 出栈
print(item)  # 'b'
2

滑动窗口算法

双端队列在解决滑动窗口最大值问题中非常高效：

def max_sliding_window(nums, k):
    if not nums:
        return []
    
    result = []
    dq = deque()  # 存储索引
    
    for i in range(len(nums)):
        # 移除超出窗口范围的索引
        if dq and dq[0] == i - k:
            dq.popleft()
        
        # 移除小于当前元素的索引
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # 当窗口形成时记录最大值
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # [3, 3, 5, 5, 6, 7]
3

回文检查

双端队列是检查字符串是否为回文的理想工具：

def is_palindrome(s):
    dq = deque(s.lower().replace(' ', ''))
    
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

# 示例
print(is_palindrome("A man a plan a canal Panama"))  # True
print(is_palindrome("Python"))  # False

deque vs list 性能对比

在队列操作中，deque比Python列表(list)性能更高：

操作 deque list 性能差异
appendleft/popleft O(1) O(n) deque显著更快
append/pop O(1) O(1) 相当
随机访问 O(n) O(1) 列表更快
中间插入/删除 O(n) O(n) 相当

结论

Python的collections.deque是处理双端队列操作的理想选择。当需要频繁在序列两端添加或删除元素时，deque提供了比列表更优的性能。

关键点总结：

  • 使用deque实现队列(FIFO)和栈(LIFO)
  • 在滑动窗口算法中高效维护窗口
  • 线程安全，适合多线程环境
  • 指定maxlen参数创建有限长度队列
  • 避免使用deque进行随机访问和中间操作