deque替代list做队列仅在频繁头部增删时有意义；因list基于动态数组，pop(0)/insert(0,x)需移动后续所有元素，时间复杂度O(n)，而deque为块状链表，popleft()/appendleft()均为O(1)。
用 deque 替代 list 做队列操作，只有在频繁从**头部增删**（appendleft() / popleft()）时才真正有意义；如果只是尾部操作或随机访问，list 反而更快、更省内存。
为什么 list.pop(0) 和 list.insert(0, x) 性能差？
list 是基于动态数组实现的，pop(0) 或 insert(0, x) 需要把后面所有元素逐个前移或后挪，时间复杂度是 O(n)。10 万个元素的 list 调用一次 pop(0)，可能卡住几十毫秒。
而 deque 是双向链表（实际是块状链表，兼顾缓存友好性），popleft() 和 appendleft() 都是 O(1) —— 不管容器多大，耗时基本恒定。
- 典型误用场景：用
list实现 BFS 队列，每次queue.pop(0)拖慢整个遍历 - 正确做法：改用
deque，queue.popleft() - 注意：
deque的pop()和append()（尾部）也是 O(1)，和list尾部操作性能相当
deque 初始化和常用操作对比
初始化方式几乎一样，但语义和行为有关键差异：
立即学习“Python免费学习笔记（深入）”；
-
from collections import deque—— 必须显式导入，不能直接用deque() -
d = deque([1,2,3])和l = [1,2,3]看似一样，但d[0]和d[-1]是 O(1)，d[5000]是 O(n)；而list所有索引都是 O(1) -
d.appendleft(x)/d.popleft()安全可用；l.insert(0, x)/l.pop(0)应该避免 -
len(d)是 O(1)；len(l)也是 O(1)，这点没区别
示例：
from collections import deque q = deque() q.append(1) # → deque([1]) q.appendleft(0) # → deque([0, 1]) q.popleft() # → 0，q 变成 deque([1])
哪些情况别硬换 deque？
不是所有“看起来像队列”的地方都适合 deque：
- 需要大量随机索引访问（如
d[i]循环遍历）→ 用list更快 - 只做尾部操作（
append()+pop()），且不关心头部 →list内存更紧凑，CPU 缓存更友好 - 数据量极小（
-
deque不支持切片（d[1:3]报TypeError），也不能用in高效查找（O(n) 且无优化）
真正要盯住的是操作模式：只要逻辑上需要「从头取、往头塞」，哪怕只比 list 快几微秒，积少成多就容易变成瓶颈——这时候 deque 就不是“可选优化”，而是必要选择。
