Python 中的 deque 是一个低级别的、高度优化的双端队列，对于实现优雅、高效的Pythonic 队列和堆栈很有用，它们是计算中最常见的列表式数据类型。
本文中，云朵君将和大家一起学习如下：
向 Python 列表的右端追加元素和弹出元素的操作，一般非常高效。如果用大 O 表示时间复杂性，那么可以说它们是 O(1)。而当 Python 需要重新分配内存来增加底层列表以接受新的元素时，这些操作就会变慢，时间复杂度可能变成 O(n)。
此外，在 Python 列表的左端追加和弹出元素的操作，也是非常低效的，时间复杂度为O(n)。
由于列表提供了 .append() 和 .pop() 这两种操作，它们可以作为堆栈和队列使用。而列表的左右端追加和弹出操作的性能问题会大大影响应用程序的整体性能。
Python 的 deque 是早在 Python 2.4 中添加到 collections 模块的第一个数据类型。这个数据类型是专门为克服 Python list 中的 .append()和 .pop() 的效率问题而设计的。
Deques是类似于序列的数据类型，被设计为堆栈和队列的一般化，它们在数据结构的两端支持高效的内存和快速的追加和弹出操作。
在 deque 对象两端的追加和弹出操作是稳定的，而且同样有效，因为 deque 是作为双链接列表实现。此外，deque 上的追加和弹出操作也是线程安全的和内存高效的。这些特性使得 deque 在Python中创建自定义栈和队列时特别有用。
如果需要保存最后看到的元素列表，也可以使用 deque，因为可以限制 deque 的最大长度。如果我们这样做了，那么一旦 deque 满了，当我们在另一端添加新的元素时，它会自动丢弃一端的元素。
下面是 deque 的主要特点的总结：
创建 deque 实例比较简单。只需要从 collection 中导入 deque，然后用一个可选的迭代器作为参数来调用它。
选项描述.insert(i, value)在索引为i的deque容器中插入一个名为value的元素。.remove (value)删除第一个出现的 value ，如果 value 不存在则引发ValueErrora_deque[i]从一个deque容器中检索索引为 i 的项。del a_deque[i]从deque容器中移除索引为 i 的项。我们可以使用这些方法和技术来处理 deque 对象内部任何位置的元素。下面是如何做到这一点的。>>> from collections import deque
>>> letters = deque("abde")
>>> letters.insert(2, "c")
>>> letters
deque(['a', 'b', 'c', 'd', 'e'])
>>> letters.remove("d")
>>> letters
deque(['a', 'b', 'c', 'e'])
>>> letters[1]
'b'
>>> del letters[2]
>>> letters
deque(['a', 'b', 'e'])在这里，首先将"c"插入到位置 2的letters中。然后使用 .remove() 从deque容器中移除"d"。Deque 还允许索引来访问元素，在这里使用它来访问索引1处的b。最后，你可以使用 del 关键字从 deque 中删除任何存在的项。请注意， .remove() 允许按值删除项，而del则按索引删除项。
尽管 deque 对象支持索引，但它们不支持切片，即不能像常规列表一样使用切片语法， [start:stop:step] 从现有的 deque 中提取：
运作dequelist通过索引访问任意的元素O(n)O(1)在左端弹出和追加元素O(1)O(n)在右端弹出和追加元素O(1)O(1) + 重新分配在中间插入和删除元素O(n)O(n)对于列表，当解释器需要扩大列表以接受新项时，.append()的性能优势受到内存重新分配的影响而被降低。此操作需要将所有当前项复制到新的内存位置，这将极大地影响性能。此总结可以帮助我们为手头的问题选择适当的数据类型。但是，在从列表切换到 deque 之前，一定要对代码进行剖析，它们都有各自的性能优势。用Deque构建高效队列Deque 是一个双端队列，提供了堆栈和队列的泛化。在本节中，我们将一起学习如何使用deque以优雅、高效和Pythonic的方式在底层实现我们自己的队列抽象数据类型（ADT）。注意： 在 Python 标准库中，queue 模块实现了多生产者、多消费者的队列，可以在多个线程之间安全地交换信息。如果你正在处理队列，那么最好使用那些高级抽象而不是 deque ，除非你正在实现自己的数据结构。队列是元素的collections，可以通过在一端添加元素和从另一端删除元素来修改队列。队列 以先入先出（FIFO）的方式管理元素，像一个管道一样工作，在管道的一端推入新元素，并从另一端弹出旧元素。向队列的一端添加一个元素称为 enqueue 操作；从另一端删除一个元素称为 dequeue。为了更好地理解队列，以餐厅为例，餐馆里有很多人在排队等着点餐。通常情况下，后来的人将排在队列的末端。一旦有了空桌子，排在队伍开头的人就会离开队伍进去用餐。下面演示了使用一个原始的deque对象来模拟这个过程。>>> from collections import deque
>>> customers = deque()
>>> # People arriving
>>> customers.append("Jane")
>>> customers.append("John")
>>> customers.append("Linda")
>>> customers
deque(['Jane', 'John', 'Linda'])
>>> # People getting tables
>>> customers.popleft()
'Jane'
>>> customers.popleft()
'John'
>>> customers.popleft()
'Linda'
>>> # No people in the queue
>>> customers.popleft()
Traceback (most recent call last):
File "", line 1, in
IndexError: pop from an empty deque首先创建一个空的 deque 对象来表示到达餐厅的人的队列。person排队放入队列，可以使用.append()，将单个条目添加到右端。要从队列中取出一个person，可以使用.popleft() ，删除并返回deque容器左侧的各个条目。
用队列模拟工作，然而，由于deque是一个泛化，它的API]不匹配常规的队列API。例如，不是.enqueue()，而是.append()。还有.popleft() 而不是.dequeue()。此外，deque 还提供了其他一些可能不符合特定需求的操作。
我们可以创建具有特定功能的自定义队列类。可以在内部使用 deque 来存储数据，并在自定义队列中提供所需的功能。我们可以把它看作是适配器设计模式的一个实现，在这个模式中，把 deque 的接口转换成看起来更像队列接口的东西。
例如，需要一个自定义的队列抽象数据类型，提供以下功能。
此时可以写一个Queue类。
MethodSupport.__len__ ()长度的 len().__contains__()带有in的成员测试.__iter__()常规迭代.__reversed__()反向迭代.__repr__()字符串表示形式理想情况下，.__repr__()返回一个字符串，代表一个有效的 Python 表达式。可以用这个表达式以相同的值重新创建这个对象。然而，在上面的例子中，目的是使用方法的返回值在 interactive shell 上优雅地显示对象。可以通过接受初始化可迭代对象作为.__init__() 的参数并从中构建实例，从而从这个特定的字符串表示形式构建 Queue 实例。有了这些补充，Queue 类就完成了。要在我们的代码中使用这个类，我们可以做如下事情。>>> from custom_queue import Queue
>>> numbers = Queue()
>>> numbers
Queue([])
>>> # Enqueue items
>>> for number in range(1, 5):
... numbers.enqueue(number)
...
>>> numbers
Queue([1, 2, 3, 4])
>>> # Support len()
>>> len(numbers)
4
>>> # Support membership tests
>>> 2 in numbers
True
>>> 10 in numbers
False
>>> # Normal iteration
>>> for number in numbers:
... print(f"Number: {number}")
...
1
2
3
4队列和堆栈是编程中常用的 抽象数据类型。它们通常需要在底层数据结构的两端进行有效的 pop 和 append 操作。Python 的 collections 模块提供了一种叫做 deque 的数据类型，它是专门为两端的快速和节省内存的追加和弹出操作而设计的。
有了deque，我们可以用优雅、高效和Pythonic的方式在低层次上编写我们自己的队列和堆栈。
总结下本文所学内容：
