collections.deque比list更适合做队列，因其两端操作均为O(1)，而list的pop(0)或insert(0,x)为O(n)，需移动所有后续元素；deque底层基于块状双向链表实现，适用于BFS、滑动窗口等高频双端操作场景。
为什么deque比list更适合做队列
Python 的 list 在尾部 append() 和 pop() 是 O(1) 的，但头部的 insert(0, x) 或 pop(0) 是 O(n)，因为要整体移动后续元素。而 deque（双端队列）底层用双向链表+块数组实现，两端操作都是 O(1)，真正适合 FIFO 场景。
如果你的代码里频繁出现 queue.pop(0) 或 queue.insert(0, x)，基本可以断定是性能瓶颈点——尤其当队列长度常达几百以上时，延迟会明显可感。
python-script-generator
下载
快速生成专业的 Python 脚本和应用代码。一键创建完整项目结构，支持CLI、API、爬虫、Bot、Django等多种项目类型，包含完整的项目结构、配置文件、依赖管理、测试、README和文档。
怎么把现有 list 队列替换成 deque
直接替换构造和常用方法即可，接口高度兼容，但要注意语义差异：
- 用
from collections import deque 导入，初始化写成 q = deque() 或 deque([1, 2, 3])
-
q.append(x)（尾进）和 q.popleft()（头出）是标准队列操作；别用 q.pop()（那是尾出）
-
q[0] 和 q[-1] 支持 O(1) 索引访问首尾，但中间索引如 q[5] 是 O(n)，慎用
- 如果原逻辑依赖
list.index() 或切片（如 queue[:3]），deque 不支持，得转成 list(q) 再操作——这步是 O(n)，别放在热路径里
哪些场景下 deque 反而更慢
不是所有“像队列”的地方都该换 deque：
- 纯栈行为（只用
append() + pop()）：list 更快，因为局部性好、内存连续
- 队列极短（长度稳定 deque 对象本身有额外开销，反而不如
list
- 需要频繁遍历或随机读取中间元素：比如循环中写
for i in range(len(q)): x = q[i]，这时 deque 的索引性能会拖垮整体
- 用
deque 做唯一容器，却反复调用 len(q) ——虽然也是 O(1)，但比 list 的 len 略重，不过这点通常可忽略
一个典型误用：用 deque 实现 LRU 缓存
很多人第一反应是“LRU 要删头加尾，deque 天然合适”，但漏了关键点：LRU 需要 O(1) 查找 key 是否存在，并把对应节点移到尾部。deque 本身不支持按值查找或移动中间节点。
from collections import deque 导入，初始化写成 q = deque() 或 deque([1, 2, 3])
q.append(x)（尾进）和 q.popleft()（头出）是标准队列操作；别用 q.pop()（那是尾出）q[0] 和 q[-1] 支持 O(1) 索引访问首尾，但中间索引如 q[5] 是 O(n)，慎用list.index() 或切片（如 queue[:3]），deque 不支持，得转成 list(q) 再操作——这步是 O(n)，别放在热路径里deque：
- 纯栈行为（只用
append()+pop()）：list更快，因为局部性好、内存连续 - 队列极短（长度稳定 deque 对象本身有额外开销，反而不如
list - 需要频繁遍历或随机读取中间元素：比如循环中写
for i in range(len(q)): x = q[i]，这时deque的索引性能会拖垮整体 - 用
deque做唯一容器，却反复调用len(q)——虽然也是 O(1)，但比list的len略重，不过这点通常可忽略
一个典型误用：用 deque 实现 LRU 缓存
很多人第一反应是“LRU 要删头加尾，deque 天然合适”，但漏了关键点：LRU 需要 O(1) 查找 key 是否存在，并把对应节点移到尾部。deque 本身不支持按值查找或移动中间节点。
正确做法是组合使用：dict 存 key→value 映射 + deque 存 key 的访问顺序，但每次 get 时仍需 deque.remove(key) ——这个操作是 O(n)。所以真要高性能 LRU，得用 OrderedDict（Python 3.7+ 的 dict 也保持插入序）或手写哈希链表。
deque 可能修复了一个慢点，又埋下另一个更难察觉的慢点。 
