算法_Deque队列的使用

deque 的核心操作演示

1. 创建 deque

1
2
3
4
5
6
7
from collections import deque
# 创建空队列
q1 = deque()
# 创建包含初始元素的队列
q2 = deque([1, 2, 3])  # deque([1, 2, 3])
# 指定最大长度（超过自动删除左侧元素）
q3 = deque(maxlen=3)

2. 入队操作（添加元素）

1
2
3
4
5
6
7
8
9
q = deque([1, 2])
# 右侧添加（最常用）
q.append(3)        # deque([1, 2, 3])
# 左侧添加（层序遍历用不到）
q.appendleft(0)    # deque([0, 1, 2, 3])

# 批量添加
q.extend([4, 5])   # deque([0, 1, 2, 3, 4, 5])
q.extendleft([-1]) # 注意：extendleft会逆序添加

3. 出队操作（取出元素）

1
2
3
4
5
q = deque([1, 2, 3, 4])
# 左侧取出（层序遍历用这个）
x = q.popleft()    # x = 1, 队列变为 deque([2, 3, 4])
# 右侧取出（栈的操作）
y = q.pop()        # y = 4, 队列变为 deque([2, 3])

4. 查看元素（不取出）

1
2
3
4
5
6
7
q = deque([1, 2, 3])
# 查看左侧第一个
first = q[0]       # 1（不会删除）
# 查看右侧第一个
last = q[-1]       # 3（不会删除）
# 查看所有元素
list(q)            # [1, 2, 3]

5. 其他常用操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
q = deque([1, 2, 3])

# 获取长度
size = len(q)      # 3

# 清空队列
q.clear()          # deque([])

# 判断是否为空
if q:  # 如果q不为空
    print("队列非空")

# 反转队列
q = deque([1, 2, 3])
q.reverse()        # deque([3, 2, 1])

# 旋转队列
q.rotate(1)        # 向右旋转1步：deque([3, 1, 2])
q.rotate(-1)       # 向左旋转1步：deque([1, 2, 3])

五、为什么不用 list 而用 deque？

1
2
3
4
5
6
7
8
9
10
# 用 list 模拟队列（不推荐）
queue = []
queue.append(1)        # 入队 O(1)
x = queue.pop(0)       # 出队 O(n) ❌ 因为要移动后面的所有元素

# 用 deque 实现队列（推荐）
from collections import deque
queue = deque()
queue.append(1)        # 入队 O(1)
x = queue.popleft()    # 出队 O(1) ✅ 专门优化过

关键区别：

  • list.pop(0) 的时间复杂度是 O(n)（需要移动所有元素）
  • deque.popleft() 的时间复杂度是 O(1)（专门优化）

七、常见的 deque 使用场景

场景1：二叉树层序遍历（你的代码）

1
2
3
4
5
6
7
8
9
10
def levelOrder(root):
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)

场景2：滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxSlidingWindow(nums, k):
    dq = deque()  # 存储索引
    result = []
    
    for i, num in enumerate(nums):
        # 移除超出窗口左侧的元素
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 维护单调递减
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

场景3：最近使用缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
class LRUCache:
    def __init__(self, capacity):
        self.cache = {}
        self.used = deque()
        self.capacity = capacity
    
    def get(self, key):
        if key in self.cache:
            # 移动到最近使用
            self.used.remove(key)
            self.used.append(key)
            return self.cache[key]
        return -1