Deque in Python is a low-level, highly optimized double-ended queue, useful for implementing elegant and efficient Pythonic queues and stacks, which are the most common list-based data types in computing.
In this article, Mr. Yun Duo will learn the following together with you:
The operation of appending elements to the right end of the Python list and popping elements is generally very efficient. If time complexity is expressed in Big O, then we can say that they are O(1). When Python needs to reallocate memory to increase the underlying list to accept new elements, these operations will slow down and the time complexity may become O(n).
In addition, the operations of appending and popping elements to the left end of the Python list are also very inefficient, with a time complexity of O(n).
Since lists provide .append() and .pop() operations, they can be used as stacks and queues. The performance issues of appending and popping operations on the left and right ends of the list will greatly affect the overall performance of the application.
Python’s deque was the first data type added to the collections module as early as Python 2.4. This data type is specifically designed to overcome the efficiency issues of .append() and .pop() in Python lists.
Deques are sequence-like data types designed as a generalization of stacks and queues. They support memory-efficient and fast append and pop operations on both ends of the data structure.
Append and pop operations on both ends of a deque object are stable and equally efficient because the deque is implemented as a doubly linked list. Additionally, append and pop operations on deque are also thread-safe and memory-efficient. These features make deque particularly useful for creating custom stacks and queues in Python.
If you need to save the last seen element list, you can also use deque, because the maximum length of deque can be limited. If we do this, then once the deque is full, it will automatically discard the elements at one end when we add new elements at the other end.
The following is a summary of the main features of deque:
Creating a deque instance is relatively simple. Just import deque from the collection and call it with an optional iterator as argument.
>>> from collections import deque
>>> # 创建一个空的 deque
>>> deque()
deque([])
>>> # 使用不同的迭代器来创建 deque
>>> deque((1, 2, 3, 4))
deque([1, 2, 3, 4])
>>> deque([1, 2, 3, 4])
deque([1, 2, 3, 4])
>>> deque(range(1, 5))
deque([1, 2, 3, 4])
>>> deque("abcd")
deque(['a', 'b', 'c', 'd'])
>>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4}
>>> deque(numbers.keys())
deque(['one', 'two', 'three', 'four'])
>>> deque(numbers.values())
deque([1, 2, 3, 4])
>>> deque(numbers.items())
deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])If you instantiate deque without providing iterable as a parameter, you will get an empty deque. If an iterable is provided and entered, the deque initializes a new instance with its data. Initialization proceeds from left to right using deque.append().
Deque initializer requires the following two optional parameters.
As mentioned before, if you don't provide an iterable, then you will get an empty deque. If you provide a value for maxlen, then your deque will only store the items up to maxlen.
Finally, you can also use unordered iterable objects, such as collections, to initialize deque. In these cases, there will be no predefined order of elements in the final deque.
The most important difference between Deque and List is that the former can perform efficient appending and popping operations at both ends of the sequence. The Deque class implements specialized .popleft() and .appendleft() methods to directly operate on the left end of the sequence.
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.popleft() 1 >>> numbers.popleft() 2 >>> numbers deque([3, 4]) >>> numbers.appendleft(2) >>> numbers.appendleft(1) >>> numbers deque([1, 2, 3, 4])
Here, use .popleft() and .appendleft() to pop up and increase the left end value of numbers respectively. These methods are designed for deque, and list has no such method.
Deque also provides .append() and .pop() methods like list to operate on the right end of the sequence. However, the behavior of .pop() is different.
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.pop() 4 >>> numbers.pop(0) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: pop() takes no arguments (1 given)
Here, .pop() removes and returns the last element in the deque container. This method does not accept an index as a parameter, so it cannot be used to remove arbitrary items from the deque. You can only use it to remove and return the rightmost item.
We think deque is a doubly linked list. Therefore, each item in a given deque container holds a reference (pointer) to the previous and next item in the sequence.
Double linked lists make the operation of adding and popping elements from both ends simple and efficient, because only the pointers need to be updated, therefore, the two operations have similar performance, both are O(1). They are also predictable in terms of performance because there is no need to reallocate memory and move existing items to accept new items.
从常规 Python 列表的左端追加和弹出元素需要移动所有元素，这最终是一个 O(n) 操作。此外，将元素添加到列表的右端通常需要Python重新分配内存，并将当前项复制到新的内存位置，之后，它可以添加新项。这个过程需要更长的时间来完成，并且追加操作从 O(1)传递到 O(n)。
考虑以下关于在序列左端添加项的性能测试，deque vs list。
# time_append.py
from collections import deque
from time import perf_counter
TIMES = 10_000
a_list = []
a_deque = deque()
def average_time(func, times):
total = 0.0
for i in range(times):
start = perf_counter()
func(i)
total += (perf_counter() - start) * 1e9
return total / times
list_time = average_time(lambda i: a_list.insert(0, i), TIMES)
deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES)
gain = list_time / deque_time
print(f"list.insert(){list_time:.6} ns")
print(f"deque.appendleft() {deque_time:.6} ns({gain:.6}x faster)")在这个脚本中，average_time() 计算了执行一个给定次数的函数（func）的平均时间。如果我们在命令行中运行该脚本，那么我们会得到以下输出。
$ python time_append.py list.insert()3735.08 ns deque.appendleft() 238.889 ns(15.6352x faster)
在这个例子中，deque 上的 .appendleft() 要比 list 上的 .insert() 快几倍。注意 deque.appendleft() 执行时间是常量O(1)。但列表左端的 list.insert() 执行时间取决于要处理的项的数量O(n)。
在这个例子中，如果增加 TIMES 的值，那么 list.insert() 会有更高的时间测量值，而 deque.appendleft() 会得到稳定(常数)的结果。如果对 deque 和 list 的 pop 操作进行类似的性能测试，那么可以展开下面的练习块。
Exercise：测试 deque.popleft() 与 list.pop(0) 的性能
可以将上面的脚本修改为时间deque.popleft()与list.pop(0)操作并估计它们的性能。
Solution：测试 deque.popleft() 与 list.pop(0) 的性能
# time_pop.py
from collections import deque
from time import perf_counter
TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)
def average_time(func, times):
total = 0.0
for _ in range(times):
start = perf_counter()
func()
total += (perf_counter() - start) * 1e9
return total / times
list_time = average_time(lambda: a_list.pop(0), TIMES)
deque_time = average_time(lambda: a_deque.popleft(), TIMES)
gain = list_time / deque_time
print(f"list.pop(0) {list_time:.6} ns")
print(f"deque.popleft() {deque_time:.6} ns({gain:.6}x faster)")list.pop(0) 2002.08 ns deque.popleft() 326.454 ns(6.13282x faster) 同样，它deque比list从底层序列的左端删除元素要快。 尝试更改TIMES的值，看看会发生什么
Deque 数据类型的设计是为了保证在序列的两端进行有效的追加和弹出操作。它是处理需要在 Python 中实现队列和堆栈数据结构的问题的理想选择。
Python 的 deque 返回可变的序列，其工作方式与列表相当类似。除了可以有效地从其末端追加和弹出元素外，deque 还提供了一组类似列表的方法和其他类似序列的操作，以处理任意位置的元素。下面是其中的一些。
选项 | 描述 |
.insert(i, value) | 在索引为i的deque容器中插入一个名为value的元素。 |
.remove (value) | 删除第一个出现的 value ，如果 value 不存在则引发ValueError |
a_deque[i] | 从一个deque容器中检索索引为 i 的项。 |
del a_deque[i] | Removes the item with index i from the deque container. |
我们可以使用这些方法和技术来处理 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 中提取：
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4, 5]) >>> numbers[1:3] Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: sequence index must be integer, not 'slice'
Deque支持索引，却不支持分片。通常来说在一个链表上执行切片非常低效。
虽然 deque 与 list 非常相似，但 list 是基于数组的，而 deque 是基于双链表的。
Deque 基于双链表，在访问、插入和删除任意元素都是无效操作。如果需要执行这些操作，则解释器必须在deque中进行迭代，直到找到想要的元素。因而他们的时间复杂度是O(n)而不是O(1)。
下面演示了在处理任意元素时 deques 和 list 的行为。
# time_random_access.py
from collections import deque
from time import perf_counter
TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)
def average_time(func, times):
total = 0.0
for _ in range(times):
start = perf_counter()
func()
total += (perf_counter() - start) * 1e6
return total / times
def time_it(sequence):
middle = len(sequence) // 2
sequence.insert(middle, "middle")
sequence[middle]
sequence.remove("middle")
del sequence[middle]
list_time = average_time(lambda: time_it(a_list), TIMES)
deque_time = average_time(lambda: time_it(a_deque), TIMES)
gain = deque_time / list_time
print(f"list{list_time:.6} μs ({gain:.6}x faster)")
print(f"deque {deque_time:.6} μs")这个脚本对插入、删除和访问一个 deque 和一个 list 中间的元素进行计时。如果运行这个脚本，得到如下所示的输出:
$ python time_random_access.py list63.8658 μs (1.44517x faster) deque 92.2968 μs
Deque并不像列表那样是随机访问的数据结构。因此，从 deque 的中间访问元素的效率要比在列表上做同样的事情低。这说明 deque 并不总是比列表更有效率。
Python 的 deque 对序列两端的操作进行了优化，所以它们在这方面一直比 list 好。另一方面，列表更适合于随机访问和固定长度的操作。下面是 deque 和 list 在性能上的一些区别。
运作 | | |
通过索引访问任意的元素 | O(n) | O(1) |
在左端弹出和追加元素 | O(1) | O(n) |
Pop and append elements at the right end | O (1) | ##O(1) Redistribute |
| Insert and delete elements in the middle | O(n) | O(n) |
Method | Support |
| length of |
| ## .__contains__( ) | Member test with in |
| .__iter__() | Regular iteration |
| .__reversed__() | Reverse iteration |
| .__repr__() | String representation |
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
