python - 合并两个双端队列 O(1)

Question

有没有办法合并两个Python deques在 O(1) 中？

Double linked lists可以在O(1)中进行合并，而deque是双链表的实现。但是，从文档中我没有看到有效合并两个双端队列的方法。 this question中提到的a.extend(b)和a += b实际上是迭代 b 的所有元素，因此时间复杂度是 O(len(b)) 而不是 O(1)。

Answer 1

不。 deque 不是普通的双向链表。它们是多个值 block 的链接列表(在 CPython 引用解释器上，每个 block 最多可以包含 64 个值)，其中只有开始和结束 block 可能不完整；没有一个 block 可能是稀疏的。因此它必须填充左侧的结束 block ，这意味着下一个 block 将由两个 block 的混合填充，等等。

除此之外，由于Python中不存在破坏性迭代(无论如何都不支持任何语言)，因此即使左侧的结束 block 和右侧的开始 block 已满，它实际上也无法传输 block 。复制必须发生， block 所有权不能转移。