deque

在 Python 中，deque（双端队列）是 collections 模块提供的一个容器类型，全称是 “double‐ended queue”。它支持从两端高效地增删元素，适合需要频繁在队头或队尾操作的场景。

主要特点

双端操作
- 队尾增删：append(x)、pop()
- 队头增删：appendleft(x)、popleft()
固定长度
- 可在创建时指定 maxlen，当队列长度达到上限再添加新元素时，会自动从另一端溢出并丢弃最旧的元素。
高性能
- 在两端增删元素的时间复杂度均为 O(1)；而在普通 list 头部插入或删除往往是 O(n)。
旋转操作
- rotate(n)：将队列元素向右循环滑动 n 步（n 为负时向左滑动）。
线程安全
- 对同一个 deque 实例，单线程操作是安全的，但多线程环境下仍建议使用锁；不过它内部对常规操作已有一定程度的原子性保证。

常用方法

方法	功能描述
`deque([iterable], maxlen)`	构造一个双端队列，可选初始元素和最大长度
`append(x)`	在队尾添加元素 x
`appendleft(x)`	在队头添加元素 x
`pop()`	弹出并返回队尾元素
`popleft()`	弹出并返回队头元素
`extend(iterable)`	在队尾一次性添加多个元素
`extendleft(iterable)`	在队头一次性添加多个元素（结果顺序会被反转）
`rotate(n)`	将队列循环右移 `n` 次（`n<0` 时左移）
`clear()`	清空队列
`count(x)`	统计元素 x 在队列中出现的次数
`remove(x)`	删除第一个出现的元素 x

示例代码

python

from collections import deque

# 创建一个空的双端队列
dq = deque()

# 在尾部添加
dq.append(1)
dq.append(2)      # deque([1, 2])

# 在头部添加
dq.appendleft(0)  # deque([0, 1, 2])

# 弹出元素
x = dq.pop()      # x = 2, dq -> deque([0, 1])
y = dq.popleft()  # y = 0, dq -> deque([1])

# 批量添加
dq.extend([2,3,4])         # deque([1,2,3,4])
dq.extendleft([0,-1])      # deque([-1,0,1,2,3,4])

# 限定最大长度，溢出时自动丢弃对端元素
dq2 = deque(maxlen=3)
dq2.extend([1,2,3,4])      # deque([2,3,4])

# 循环旋转
dq2.rotate(1)              # deque([4,2,3])
dq2.rotate(-2)             # deque([3,4,2])

适用场景

广度优先搜索（BFS）：队列头尾操作频繁，用 deque 性能更好。
滑动窗口：maxlen 可以实现固定大小的窗口，或手动维护窗口元素并使用 popleft()。
任务调度：需要高效地在两端插入、删除任务。
缓存实现：环形缓冲区，结合 maxlen 自动丢弃旧数据。

总体来说，当你需要一个既能作为栈（stack）又能作为队列（queue）使用，且对头尾操作性能有严格要求时，collections.deque 是比普通列表更优的选择。

solution

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        ans = []
        while queue:
            v = []
            # 这里的逻辑很重要，获取当前queue的长度，将当前的queue的元素都dequeue出来。
            for _ in range(len(queue)):
                node = queue.pop(0)
                v.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            ans.append(v)
        return ans