Python中collections.deque双边队列的工作原理是怎样的？

本文共计1107个文字，预计阅读时间需要5分钟。

队列是一种线性表，它只允许在一端进行插入操作，在另一端进行删除操作。在Python文档中，搜索队列（queue）会发现Python标准库中包含了四种队列类型，分别是：`queue.Queue`、`asyncio.Queue`、`queue.LifoQueue`和`queue.PriorityQueue`。

队列是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

在Python文档中搜索队列（queue）会发现，Python标准库中包含了四种队列，分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。

collections.deque

deque是双端队列（double-ended queue）的缩写，由于两端都能编辑，deque既可以用来实现栈（stack）也可以用来实现队列（queue）。

deque支持丰富的操作方法，主要方法如图：

相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现在出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。