Python 的 deque 是什么？为什么用它而不是 list 做队列？

简化版

**collections.deque（double-ended queue，双端队列）是一个「两端都能高效增删」的序列——在头部和尾部添加/弹出元素都是 O(1)，而 list 在头部操作（insert(0, x)、pop(0)）是 O(n)，所以做「队列」「双端队列」要用 deque 而不是 list。**核心原因：list 底层是动态数组，头部插入/删除要把后面所有元素整体搬移一位（O(n)）；deque 底层是双向链表（分块），两端操作只改指针（O(1)）。常用方法：append(x)/appendleft(x)（右/左加）、pop()/popleft()（右/左弹）、extend/extendleft、rotate(n)（循环移位）。独特功能 maxlen：deque(maxlen=n) 是「有界队列」——满了再从一端加，另一端会自动挤掉元素，天然适合「保留最近 N 条」（滑动窗口、最近记录）。代价：deque 不支持高效的「随机中间访问」（d[i] 是 O(n)，list 是 O(1)）——deque 擅长两端、list 擅长随机访问。核心记忆：deque 双端 O(1)（list 头部 O(n)），做队列/双端队列用它，maxlen 做有界窗口；随机中间访问用 list。

详细版

deque vs list 的复杂度对比：

操作	list	deque
尾部 append/pop	O(1)	O(1)
头部 insert(0)/pop(0)	O(n)	O(1)（appendleft/popleft）
随机访问 `d[i]`	O(1)	O(n)（中间）
长度 len	O(1)	O(1)

from collections import deque

# 创建
d = deque([1, 2, 3])
d = deque(maxlen=3)             # 有界队列

# 两端操作（都是 O(1)）
d = deque([2, 3])
d.append(4)                    # 右加 → [2,3,4]
d.appendleft(1)                # 左加 → [1,2,3,4]
d.pop()                        # 右弹 → 4，剩 [1,2,3]
d.popleft()                    # 左弹 → 1，剩 [2,3]

# 队列（FIFO）：右进左出
q = deque()
q.append("task1"); q.append("task2")
q.popleft()                    # "task1"（先进先出）

# rotate 循环移位
d = deque([1,2,3,4,5])
d.rotate(2)                    # 右移2 → [4,5,1,2,3]
d.rotate(-1)                   # 左移1 → [5,1,2,3,4]

# maxlen：有界队列，满了自动挤掉另一端
recent = deque(maxlen=3)
for i in range(5):
    recent.append(i)          # 满3后，新加挤掉最旧
print(recent)                 # deque([2,3,4], maxlen=3)（只留最近3个）

# 对比 list 做队列（慢！）
lst = [1,2,3]
lst.pop(0)                    # O(n) —— 后面元素全搬移一位

⚠️ 一句话抓住本质：deque 和 list 是「为不同访问模式优化的两种序列」——list 是动态数组（随机访问 O(1)、但头部增删要搬移整个数组 O(n)），deque 是分块双向链表（两端增删 O(1)、但中间随机访问 O(n)）；做队列/两端操作用 deque，做随机索引/末尾追加用 list。最常见的错误是「用 list 当队列」：queue.pop(0) 每次都要把剩下的 n-1 个元素整体前移一位，n 大时性能灾难；deque.popleft() 只改一下头指针、O(1)。deque 还有两个 list 没有的亮点：① maxlen 有界队列——deque(maxlen=100) 永远只保留最近 100 个，满了自动从另一端挤出，做「滑动窗口/最近日志/最近 N 次记录」一行搞定，不用手动裁剪；② rotate(n) 循环移位、以及 appendleft/popleft/extendleft 这套「左端」操作。deque 也是线程安全的（append/pop 两端操作是原子的），可直接用作简单的多线程队列（虽然更完整的用 queue.Queue）。

完整版教学

一、deque 是什么

先理解 deque 的定位：

collections.deque（双端队列，double-ended queue）：
  一个"两端都能高效增删"的序列容器
  读音 "deck"

核心特性：
  ① 头尾增删都是 O(1)
     append/appendleft（加）、pop/popleft（弹）
  ② 可选 maxlen（有界队列，满了自动挤出）
  ③ 支持大部分序列操作（len、in、索引、迭代、切片*）
     *切片要用 itertools.islice，不直接支持 d[1:3]

创建：
  deque()                    # 空
  deque([1,2,3])             # 从可迭代对象
  deque(maxlen=5)            # 有界（最多 5 个）
  deque([1,2,3], maxlen=5)   # 从数据 + 有界

底层实现：
  分块的双向链表（block of arrays）
  → 两端是块的两头，增删只改指针/块（O(1)）
  → 不是连续数组，随机访问要遍历块（中间 O(n)）

定位：
  需要"队列/双端队列/两端频繁增删/有界窗口" → deque
  需要"随机索引访问、末尾追加为主" → list

所以 deque 是双端队列,头尾增删 O(1),底层分块双向链表,可设 maxlen

collections.deque（双端队列，读音 “deck”） 是一个「两端都能高效增删」的序列容器。核心特性：① 头尾增删都是 O(1)（append/appendleft 加、pop/popleft 弹）、② 可选 maxlen（有界队列、满了自动挤出）、③ 支持大部分序列操作（len、in、索引、迭代，切片要用 itertools.islice）。创建：deque()、deque([1,2,3])、deque(maxlen=5)、deque([1,2,3], maxlen=5)。底层实现：分块的双向链表（两端是块的两头、增删只改指针 O(1)、不是连续数组随机访问要遍历块中间 O(n)）。定位：需要队列/双端队列/两端频繁增删/有界窗口用 deque、需要随机索引访问/末尾追加为主用 list。理解「deque 双端队列头尾增删 O(1);底层分块双向链表(两端 O(1)、中间随机访问 O(n));可设 maxlen 有界;需要队列/两端操作用 deque」，就理解了 deque 是什么。

二、为什么 list 做队列慢

理解 list 头部操作的 O(n) 问题：

list 底层是"动态数组"（连续内存）：
  元素在内存里连续排列
  → 随机访问 lst[i] 是 O(1)（直接算地址）
  → 末尾 append/pop 是 O(1)（在末尾操作）

但头部操作是 O(n)：
  lst.insert(0, x)：在开头插入
    → 后面所有元素都要"整体后移一位"腾位置 → O(n)
  lst.pop(0)：删除开头
    → 后面所有元素都要"整体前移一位"补空 → O(n)

图示（pop(0) 要搬移）：
  [A, B, C, D, E]  pop(0)
   ↓  删 A
  [_, B, C, D, E]  B,C,D,E 全部前移一位
  [B, C, D, E]     → 搬了 n-1 个元素

用 list 做队列的性能灾难：
  queue = []
  queue.append(x)   # 入队 O(1)
  queue.pop(0)      # 出队 O(n) ← 每次都搬移！
  → n 个元素的队列，全部出队是 O(n²)

deque 的解法：
  底层双向链表，头部有独立指针
  popleft()：改头指针 → O(1)（不搬移）
  → n 个元素全部出队是 O(n)

所以 list 头部 O(n)(要搬移整个数组),用 list 做队列 pop(0)是性能灾难

list 底层是「动态数组」（连续内存）：元素连续排列 → 随机访问 lst[i] O(1)（直接算地址）、末尾 append/pop O(1)。但头部操作是 O(n)：lst.insert(0, x)（后面所有元素整体后移一位腾位置）、lst.pop(0)（后面所有元素整体前移一位补空）。图示：pop(0) 删 A 后 B,C,D,E 全部前移一位（搬了 n-1 个）。用 list 做队列的性能灾难：queue.append(x) O(1)、queue.pop(0) O(n)（每次都搬移）——n 个元素全部出队是 O(n²)。deque 的解法：底层双向链表、头部有独立指针、popleft() 改头指针 O(1)（不搬移）——全部出队 O(n)。理解「list 底层动态数组(连续内存):随机访问/末尾 O(1)、但头部 insert(0)/pop(0)是 O(n)(要搬移整个数组);用 list 做队列 pop(0)每次搬移是 O(n²)灾难;deque 双向链表头部指针 popleft O(1)」，就理解了为什么 list 做队列慢。

三、deque 的核心方法

理解 deque 的常用操作：

两端增删（都是 O(1)）：
  append(x)       # 右端加
  appendleft(x)   # 左端加
  pop()           # 右端弹（返回）
  popleft()       # 左端弹（返回）
  extend(iter)    # 右端批量加
  extendleft(iter)# 左端批量加（注意：逆序加入！）

extendleft 的坑：
  d = deque([1,2,3])
  d.extendleft([4,5])   # 逐个 appendleft → [5,4,1,2,3]
  → 是逆序的（因为一个个从左加）

其他方法：
  d.rotate(n)     # 循环移位：n>0 右移、n<0 左移
  d[i]            # 索引访问（中间 O(n)，两端 O(1)）
  d.remove(x)     # 删第一个 x（O(n)）
  d.clear()       # 清空
  len(d), x in d  # 长度、成员判断
  reversed(d)     # 反向迭代
  d.count(x)      # 计数
  d.index(x)      # 查索引

不支持的：
  切片 d[1:3]     # ✗ 报错，要 list(itertools.islice(d,1,3))
  d.sort()        # ✗ 无 sort，要 deque(sorted(d))

队列/栈用法：
  FIFO 队列：append 入、popleft 出（右进左出）
  LIFO 栈：  append 入、pop 出（右进右出，同 list）
  双端队列：  两端都可进出

所以核心方法:append/appendleft/pop/popleft(O(1))、rotate、extendleft 逆序、不支持切片

两端增删（都是 O(1)）：append(x)（右加）、appendleft(x)（左加）、pop()（右弹）、popleft()（左弹）、extend(iter)（右批量）、extendleft(iter)（左批量）。extendleft 的坑：deque([1,2,3]).extendleft([4,5]) → [5,4,1,2,3]（逆序，因为一个个从左加）。其他方法：rotate(n)（循环移位、n>0 右移 n<0 左移）、d[i]（索引访问、中间 O(n) 两端 O(1)）、remove/clear/count/index、reversed(d)。不支持：切片 d[1:3]（要 itertools.islice）、sort（要 deque(sorted(d))）。队列/栈用法：FIFO 队列（append 入、popleft 出）、LIFO 栈（append 入、pop 出）、双端队列（两端进出）。理解「核心:append/appendleft/pop/popleft(O(1))、extend/extendleft(逆序坑)、rotate 移位、d[i]中间 O(n);不支持切片/sort;FIFO 用 append+popleft、栈用 append+pop」，就掌握了核心方法。

四、maxlen——有界队列

理解 deque 独有的 maxlen 特性：

maxlen：有界队列（deque 独有）
  deque(maxlen=n)：最多容纳 n 个元素
  满了之后再加，会从"另一端"自动挤出

行为：
  d = deque(maxlen=3)
  d.append(1)      # [1]
  d.append(2)      # [1,2]
  d.append(3)      # [1,2,3]（满）
  d.append(4)      # [2,3,4]（右加 → 左端 1 被挤出）
  d.appendleft(0)  # [0,2,3]（左加 → 右端 4 被挤出）

用途——保留"最近 N 个"：
  ① 最近 N 条日志/记录：
     recent = deque(maxlen=100)
     recent.append(log)   # 永远只留最近 100 条
  ② 滑动窗口（固定大小）：
     window = deque(maxlen=k)
     for x in stream:
         window.append(x)   # 自动维护最近 k 个
         process(window)
  ③ 移动平均：
     window = deque(maxlen=n)
     # append 后 sum(window)/len(window) 是最近 n 个的均值

好处：
  不用手动裁剪（if len > n: del d[0]）
  满了自动挤出，逻辑一行搞定

对比手写：
  list 版：append 后 if len(lst) > n: lst.pop(0)  # O(n) 且啰嗦
  deque(maxlen=n)：append 自动处理，O(1)

所以 maxlen 有界队列:满了从另一端自动挤出,做最近 N 条/滑动窗口一行搞定

maxlen：有界队列（deque 独有）——deque(maxlen=n) 最多容纳 n 个元素、满了之后再加会从「另一端」自动挤出。行为：deque(maxlen=3) 满 [1,2,3] 后 append(4) → [2,3,4]（右加、左端 1 被挤出）、appendleft(0) → [0,2,3]（左加、右端 4 被挤出）。用途——保留「最近 N 个」：① 最近 N 条日志/记录（deque(maxlen=100) 永远只留最近 100 条）、② 滑动窗口（固定大小 deque(maxlen=k) 自动维护最近 k 个）、③ 移动平均（sum(window)/len(window)）。好处：不用手动裁剪、满了自动挤出、一行搞定。对比手写：list 版 if len(lst) > n: lst.pop(0)（O(n) 且啰嗦）、deque(maxlen=n) append 自动处理 O(1)。理解「maxlen 有界队列:满了从另一端自动挤出;用途最近 N 条日志/滑动窗口/移动平均;不用手动裁剪一行搞定;比 list 手写 pop(0)省」，就掌握了 maxlen。

五、deque 的代价——中间访问慢

理解 deque 不擅长什么：

deque 的代价：中间随机访问是 O(n)

原因：底层是分块双向链表，不是连续数组
  d[i]（i 在中间）→ 要从一端遍历块找到 → O(n)
  （两端 d[0]、d[-1] 是 O(1)）

不擅长的操作：
  ① 频繁随机索引访问 d[i]（中间）→ O(n)
  ② 切片 d[i:j] → 不直接支持
  ③ 排序 → 无 sort
  → 这些用 list 更好（list 随机访问 O(1)）

deque 擅长 vs list 擅长：
  deque 擅长：两端增删、队列、有界窗口、rotate
  list 擅长：随机索引、切片、排序、末尾追加为主

选择依据（看访问模式）：
  两端进出为主       → deque
  随机访问/中间操作为主 → list
  末尾追加+随机读     → list
  队列/双端/滑动窗口   → deque

线程安全（附加优势）：
  deque 的 append/appendleft/pop/popleft 是原子操作（GIL 保证）
  → 可作简单的多线程生产者-消费者队列
  （更完整的用 queue.Queue，带阻塞/超时）

所以 deque 代价:中间随机访问 O(n)、无切片/sort;两端用 deque、随机访问用 list

deque 的代价：中间随机访问是 O(n)。原因：底层是分块双向链表不是连续数组、d[i]（i 在中间）要从一端遍历块找到（两端 d[0]、d[-1] 是 O(1)）。不擅长的操作：① 频繁随机索引访问 d[i]（中间）O(n)、② 切片不直接支持、③ 无 sort（这些用 list 更好）。deque 擅长 vs list 擅长：deque 擅长两端增删/队列/有界窗口/rotate、list 擅长随机索引/切片/排序/末尾追加。选择依据（看访问模式）：两端进出为主用 deque、随机访问/中间操作为主用 list、队列/双端/滑动窗口用 deque。线程安全（附加优势）：deque 的 append/pop 两端操作是原子的（GIL 保证）、可作简单多线程队列（更完整用 queue.Queue 带阻塞/超时）。理解「deque 代价:中间随机访问 O(n)、无切片/sort;两端进出用 deque、随机访问用 list;deque 两端操作线程安全可作简单多线程队列(完整用 queue.Queue)」，就掌握了 deque 的代价。

六、典型应用与总结

总结 deque 的应用：

典型应用：

① FIFO 队列（最常见）：
   q = deque()
   q.append(x)      # 入队
   q.popleft()      # 出队（先进先出）

② BFS 广度优先搜索：
   q = deque([start])
   while q:
       node = q.popleft()
       for nb in neighbors(node):
           q.append(nb)

③ 滑动窗口 / 最近 N 条：
   window = deque(maxlen=k)

④ 双端队列（两端都进出）：
   如单调队列（滑动窗口最大值）

⑤ 撤销/重做栈、循环缓冲

方法速查：
  append/appendleft   两端加
  pop/popleft         两端弹
  extend/extendleft   两端批量加（extendleft 逆序）
  rotate(n)           循环移位
  maxlen              有界（满了挤出）

核心总结：
  deque = 双端队列，头尾增删 O(1)（list 头部 O(n)）
  做队列/双端/BFS/滑动窗口用 deque
  maxlen 做有界窗口（最近 N 条）
  代价：中间随机访问 O(n)（随机访问用 list）
  两端操作线程安全

所以 deque 做队列/BFS/滑动窗口,两端 O(1)+maxlen 有界,随机访问用 list

典型应用：① FIFO 队列（append 入队、popleft 出队）、② BFS 广度优先搜索（q.popleft() 取节点、q.append(nb) 加邻居）、③ 滑动窗口/最近 N 条（deque(maxlen=k)）、④ 双端队列（如单调队列滑动窗口最大值）、⑤ 撤销/重做栈、循环缓冲。方法速查：append/appendleft（两端加）、pop/popleft（两端弹）、extend/extendleft（批量、extendleft 逆序）、rotate(n)（移位）、maxlen（有界）。理解「典型应用:FIFO 队列(append+popleft)、BFS(popleft 取/append 加)、滑动窗口(maxlen)、双端队列、撤销栈;deque 两端 O(1)+maxlen 有界,做队列/BFS/窗口;随机访问用 list」，就掌握了应用与总结。

记忆钩子：「collections.deque(双端队列 double-ended queue,读 deck)两端都能高效增删:append/appendleft(右/左加)、pop/popleft(右/左弹)都是 O(1);★为什么做队列用 deque 不用 list:list 底层是动态数组(连续内存),随机访问 lst[i]和末尾 append/pop 是 O(1),但头部 insert(0)/pop(0)是 O(n)(要把后面所有元素整体搬移一位),用 list 做队列 pop(0)每次搬移是 O(n²)灾难;deque 底层分块双向链表、头部有独立指针,popleft()只改指针 O(1);★独特功能 maxlen:deque(maxlen=n)是有界队列,满了再从一端加会从另一端自动挤出,做『保留最近 N 条』(滑动窗口/最近日志/移动平均)一行搞定不用手动裁剪;代价:deque 中间随机访问 d[i]是 O(n)(list 是 O(1))、不支持切片/sort——deque 擅长两端、list 擅长随机访问;deque 两端操作线程安全(可作简单多线程队列,完整用 queue.Queue);典型应用 FIFO 队列/BFS(popleft)/滑动窗口/rotate 循环移位」。

七、常见误区与追问

误区：list 也能做队列，pop(0) 和 popleft 一样。 复杂度差很多——list 底层是动态数组，pop(0) 删除开头后要把剩下的 n-1 个元素整体前移一位补空、是 O(n)，用 list 做队列时全部出队是 O(n²) 的性能灾难；deque 底层是双向链表、popleft() 只改头指针、是 O(1)；所以做队列（尤其数据量大或高频出入队）必须用 deque。
误区：deque 各种操作都比 list 快。 不是——deque 只在「两端增删」上比 list 快（O(1) vs list 头部 O(n)），但「中间随机访问」deque 是 O(n)、list 是 O(1)（list 是连续数组、直接算地址）；deque 也不支持切片、没有 sort；所以随机索引访问、切片、排序为主的场景 list 更好；deque 和 list 是为不同访问模式优化的，按需选。
误区：deque 的 extendleft 会保持原顺序加到左边。 不会——extendleft(iterable) 是逐个 appendleft，所以结果是「逆序」的：deque([1,2,3]).extendleft([4,5]) 得到 deque([5,4,1,2,3])（先 appendleft(4) 得 [4,1,2,3]、再 appendleft(5) 得 [5,4,1,2,3]）；如果想保持 [4,5] 的顺序加到左边，要先 reverse 或用 d.extendleft(reversed([4,5]))。
误区：deque(maxlen=n) 满了再加会报错。 不会报错——maxlen 满了之后再从一端添加，会自动从「另一端」挤出（丢弃）一个元素来腾位置：满了 append 会挤掉左端最旧的、appendleft 会挤掉右端的；这正是它做「保留最近 N 条」的便利之处（自动维护固定大小、无需手动裁剪），不是错误。
追问：为什么 deque 的两端操作是 O(1)，而 list 的头部操作是 O(n)？ 因为底层数据结构不同：list 是「动态数组」——元素在内存里连续存放，好处是随机访问 lst[i] O(1)（直接按下标算地址）、末尾 append/pop O(1)，但头部插入/删除要把后面所有元素整体搬移一位来保持连续，所以是 O(n)；deque 是「分块的双向链表」——由多个小数组块用双向指针连成，两端各有指针，在两端添加/删除只需操作端点块、改指针（必要时分配/释放一个块），是 O(1)，代价是中间随机访问要从一端遍历块、O(n)；所以两端频繁增删用 deque、随机访问用 list。
追问：deque 的 maxlen 有什么用，怎么用它维护滑动窗口？ maxlen 让 deque 成为「有界队列」：deque(maxlen=k) 最多存 k 个元素，满了之后再加会自动从另一端挤掉最旧的；维护滑动窗口很方便——window = deque(maxlen=k)，然后遍历数据流 for x in stream: window.append(x)，window 会始终保持「最近 k 个元素」，无需手动删除超出的（对比 list 要写 if len(lst) > k: lst.pop(0)，既啰嗦又是 O(n)）；常见应用有保留最近 N 条日志、计算移动平均（sum(window)/len(window)）、固定大小的最近记录缓冲等。
追问：deque 适合做 BFS，为什么？还有哪些典型应用？ BFS（广度优先搜索）需要一个 FIFO 队列——从队首取出当前节点、把它的邻居加到队尾，保证「先发现的先处理」，deque 的 popleft()（取队首）和 append()（加队尾）都是 O(1)，正好高效满足；用 list 的话 pop(0) 是 O(n) 会拖慢整个 BFS；其他典型应用：① FIFO 任务队列（append 入、popleft 出）；② 双端队列算法如「滑动窗口最大值」的单调队列（两端都要操作）；③ 有界的滑动窗口/最近 N 条记录（maxlen）；④ 撤销/重做栈、循环缓冲区；⑤ 用 rotate(n) 做循环移位；此外 deque 两端操作是线程安全的原子操作，可作简单的多线程队列（更完整的带阻塞/超时用 queue.Queue）。

八、加强记忆

collections.deque（双端队列，double-ended queue，读 “deck”）两端都能高效增删：append/appendleft（右/左加）、pop/popleft（右/左弹）都是 O(1)。为什么做队列用 deque 不用 list：list 底层是动态数组（连续内存）——随机访问 lst[i] 和末尾 append/pop 是 O(1)，但头部 insert(0)/pop(0) 是 O(n)（要把后面所有元素整体搬移一位），用 list 做队列 pop(0) 每次搬移是 O(n²) 灾难；deque 底层分块双向链表、头部有独立指针，popleft() 只改指针 O(1)。独特功能 maxlen：deque(maxlen=n) 是有界队列，满了再从一端加会从另一端自动挤出，做「保留最近 N 条」（滑动窗口/最近日志/移动平均）一行搞定、不用手动裁剪。代价：deque 中间随机访问 d[i] 是 O(n)（list 是 O(1)）、不支持切片/sort——deque 擅长两端、list 擅长随机访问；deque 两端操作线程安全（可作简单多线程队列，完整用 queue.Queue）。典型应用：FIFO 队列、BFS（popleft）、滑动窗口、rotate 循环移位。一句话「deque 双端队列头尾增删 O(1)(list 头部 O(n)、pop(0)是 O(n²)灾难);底层分块双向链表(中间随机访问 O(n));maxlen 做有界窗口(最近 N 条自动挤出);做队列/BFS/滑动窗口用 deque、随机访问用 list」。

简化版

详细版