Python queues实现：collections.deque机制及链表实现队列优缺点咨询

collections.deque 完全不会出现你提到的基于list手动实现队列时的头部内存闲置问题。
你观察到的list实现队列的内存缺陷，本质是手动维护头指针的实现里，已经出队的头部元素始终被list的索引持有引用，对应的内存空间既无法被复用也无法被回收，才会造成持续的闲置浪费；而collections.deque底层基于双向链表实现，元素出队时对应的节点会直接从链表结构中摘除，没有结构再持有该节点的引用，对应的内存会被Python解释器正常回收，不存在残留的闲置空间。

• 两端操作性能稳定：入队、出队（包括双端场景下的头尾追加/弹出）的时间复杂度均为O(1)，不需要像普通数组队列那样弹出头部元素时搬移所有后续元素，也不需要像循环队列那样在扩容时执行整块内存的数据拷贝，大数量级下操作延迟波动极小。
• 无冗余内存占用：不需要像数组类实现（包括循环队列）那样提前申请连续的大块内存做预分配，内存占用随实际元素数量线性增长，不会出现预分配空间远大于实际元素量的浪费。
• 天然规避头部内存泄漏：元素出队后对应节点直接脱离链表结构，不存在手动维护头指针的数组实现里，已出队元素长期被结构引用无法释放的问题。

• 单元素内存开销更高：每个链表节点除了存储实际业务数据，还要额外存储前后节点的地址指针，同等数据规模下，内存占用比连续内存的数组实现高30%~50%（依指针位宽不同有差异）。
• 不支持O(1)随机访问：如果要访问队列中非头尾的任意位置元素，必须从头节点或尾节点开始沿指针逐一遍历，时间复杂度为O(n)，完全不适合需要频繁按索引读取元素的场景。
• 遍历性能较差：链表节点的内存地址是离散不连续的，无法触发CPU缓存的连续内存预读机制，遍历全量元素的实际运行速度远低于基于连续数组的队列实现。

内容的提问来源于stack exchange，提问作者meg hidey