Python 中的 Deque，也称为双端队列，是一种数据结构，允许您从任一端添加和删除元素。蟒蛇的collections模块为我们提供了deque类来创建双端队列。
它们与队列和堆栈不同，因为它们支持更灵活、内存效率更高，并且在某些情况下支持更快的操作。
Unlike 列表或元组，双端队列是链表，可以以很快的时间复杂度处理两端的追加和弹出操作。
这使得它适用于队列（FIFO - 先进先出）和堆栈（LIFO - 后进先出）等数据结构。
让我们继续学习 Python 双端队列教程。
在 Python 中创建双端队列
以下是如何使用以下命令创建双端队列collections module:
from collections import deque
# Create a deque
d = deque()
要将元素添加到双端队列，您可以使用append() method:
d.append('a')
d.append('b')
d.append('c')
现在，如果我们打印双端队列，我们将得到：
print(d)
Output:
deque(['a', 'b', 'c'])
在上面的代码中，我们首先导入deque类来自collections模块。然后我们创建一个双端队列d。我们使用以下命令将三个元素“a”、“b”和“c”附加到双端队列的右端append() method.
当我们打印双端队列时，我们会按照添加的顺序看到这些元素。
您还可以一次初始化具有多个元素的双端队列，并可选择设置最大长度：
d = deque(['x', 'y', 'z'], maxlen=5)
这将创建一个最大长度为 5 的双端队列。如果添加更多元素，它将自动从另一端删除元素以保持大小。
访问双端队列中的元素
访问双端队列中的元素是通过索引完成的，类似于访问列表中的元素的方式：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
# Access elements
print(d[0])
print(d[-1])
Output:
'a'
'e'
在上面的代码中，我们创建了一个双端队列d有五个元素。
当我们打印时d[0]，我们得到第一个元素“a”。当我们打印时d[-1]，我们得到最后一个元素“e”。
Python 允许负索引，其中 -1 指最后一个元素，-2 指倒数第二个元素，依此类推。
然而，与列表不同，双端队列不支持切片，因为它们被设计为主要在两端进行追加和弹出操作，因此针对此类操作进行了优化。
修改元素
以下是修改元素的方法：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
# Modify an element
d[0] = 'z'
print(d)
Output:
deque(['z', 'b', 'c', 'd', 'e'])
在这段代码中，我们首先创建一个双端队列d有五个元素。然后我们将第一个元素（索引 0 处）更改为“z”。
当我们打印双端队列时，我们看到第一个元素已被修改为“z”。
请记住，修改双端队列中的元素的时间复杂度为 O(n)，因为它必须迭代双端队列才能找到该元素。
因此，如果您需要在数据结构中间频繁修改，请选择不同的数据类型。
双端队列长度
您可以使用内置的len()获取双端队列中项目数的函数：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
print(len(d))
Output:
5
在这段代码中，我们首先创建一个双端队列d有五个元素。然后我们使用打印双端队列的长度len(d)，我们得到 5，这是双端队列中的元素数量。
您还可以检查双端队列是否为空：
# Check if deque is empty
if not d:
print("Deque is empty.")
else:
print("Deque is not empty.")
Output:
Deque is not empty.
Here, not d检查双端队列是否d是空的。如果是，它会打印“Deque isempty”。如果不是，它会打印“Deque 不为空”。
将元素添加到右端（append()）
您可以使用以下命令将元素添加到双端队列的末尾append()方法。操作方法如下：
from collections import deque
d = deque(['a', 'b', 'c'])
# Add element to the right end
d.append('d')
print(d)
Output:
deque(['a', 'b', 'c', 'd'])
在上面的代码中，我们首先创建一个双端队列d具有三个要素。然后我们使用以下命令将“d”添加到双端队列的右端append() method.
当我们打印双端队列时，我们会在双端队列的右端看到“d”。
The append()该操作的时间复杂度为 O(1)，这意味着无论双端队列有多大，它都是一个非常快的操作。
将元素添加到左端（appendleft()）
您还可以使用以下命令将元素添加到双端队列的左端appendleft()方法。就是这样：
from collections import deque
d = deque(['b', 'c', 'd'])
# Add element to the left end
d.appendleft('a')
print(d)
Output:
deque(['a', 'b', 'c', 'd'])
在上面的代码中，我们首先创建一个双端队列d具有三个要素。然后我们使用以下命令将“a”添加到双端队列的左端appendleft()方法。当我们打印双端队列时，我们会在双端队列的左端看到“a”。
如同append(), the appendleft()操作的时间复杂度也为 O(1)。
将多个元素添加到右端 (extend())
The extend()方法允许您将多个元素添加到双端队列的右端。就是这样：
from collections import deque
d = deque(['a', 'b'])
# Add multiple elements to the right end
d.extend(['c', 'd', 'e'])
print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
在上面的代码中，我们首先创建一个双端队列d有两个元素。然后我们使用以下命令将三个元素“c”、“d”和“e”添加到双端队列的右端extend() method.
当我们打印双端队列时，我们会在右端看到这些新元素。
的时间复杂度为extend()运算的复杂度为 O(k)，其中 k 是要添加的元素数量。
将多个元素添加到左端 (extendleft())
The extendleft()方法允许您将多个元素添加到双端队列的左端。操作方法如下：
from collections import deque
d = deque(['d', 'e'])
# Add multiple elements to the left end
d.extendleft(['c', 'b', 'a'])
print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
在上面的代码中，我们首先创建一个双端队列d有两个元素。然后我们使用以下命令将三个元素“c”、“b”和“a”添加到双端队列的左端extendleft()方法。当我们打印双端队列时，我们会在左端看到这些新元素。
请注意，extendleft() 方法以相反的顺序迭代输入，这可以在输出中观察到。
如同extend()，时间复杂度extendleft()运算也是O(k)。
迭代双端队列
您可以像迭代列表一样迭代双端队列。
以下是向前迭代双端队列的方法：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
# Forward iteration
for i in d:
print(i)
Output:
'a'
'b'
'c'
'd'
'e'
对于向后迭代，您可以使用reversed()功能：
# Backward iteration
for i in reversed(d):
print(i)
Output:
'e'
'd'
'c'
'b'
'a'
在上面的代码中，我们首先创建一个双端队列d有五个元素。然后，我们向前和向后迭代双端队列并打印每个元素。
对双端队列进行排序
双端队列没有内置的排序方法，但您可以使用sorted()函数从双端队列中获取排序列表。
这是一个例子：
from collections import deque
d = deque([3, 1, 4, 1, 5, 9, 2])
# Get a sorted list from the deque
sorted_d = sorted(d)
print(sorted_d)
Output:
[1, 1, 2, 3, 4, 5, 9]
在上面的代码中，我们首先创建一个双端队列d与七个元素。然后，我们创建一个排序列表sorted_d从双端队列中使用sorted()功能。
结果列表按升序排列。
请记住sorted()不会就地对双端队列进行排序，而是返回一个新列表。
这是因为双端队列的设计目的是从两端进行快速追加和弹出操作，但不适用于需要随机访问元素的排序等操作。
搜索双端队列
您可以使用以下命令在双端队列中执行线性搜索index()方法。这index()方法返回指定值第一次出现的索引。
这是一个例子：
from collections import deque
d = deque(['a', 'b', 'c', 'b', 'a'])
# Get the index of 'b'
index = d.index('b')
print(index)
Output:
1
在上面的代码中，我们首先创建一个双端队列d有五个元素。然后，我们使用index()方法获取第一次出现“b”的索引，即 1。
从双端队列中删除元素
Deque 提供了从任一端删除元素的方法：pop()从双端队列的右端删除并返回一个元素，并且popleft()从左端删除并返回一个元素。让我们看一个例子：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
# Remove elements from either end
right_end = d.pop()
left_end = d.popleft()
print(right_end)
print(left_end)
print(d)
Output:
'e'
'a'
deque(['b', 'c', 'd'])
在上面的代码中，我们首先创建一个双端队列d有五个元素。然后我们使用从右端删除一个元素pop()并从左端使用popleft().
当我们打印双端队列时，我们看到左端和右端的元素被删除了。
删除所有元素
The clear()方法从双端队列中删除所有元素：
d.clear()
print(d)
Output:
deque([])
在这里，调用后d.clear()，双端队列中的所有元素都被删除，我们得到一个空双端队列作为输出。
时间复杂度为pop(), popleft(), and clear()运算复杂度为 O(1)。
双端队列轮换
双端队列提供了一个rotate()方法，允许您将双端队列向右旋转 n 步。如果n为负数，则向左旋转。
这是一个例子：
from collections import deque
d = deque(['a', 'b', 'c', 'd', 'e'])
# Rotate deque by 2 steps to the right
d.rotate(2)
print(d)
Output:
deque(['d', 'e', 'a', 'b', 'c'])
在上面的代码中，我们首先创建一个双端队列d有五个元素。
然后我们使用以下方法将双端队列向右旋转 2 步rotate(2)。最后两个元素被移至双端队列的前面。
负旋转
如果旋转负值，它将向左旋转：
# Rotate deque by 2 steps to the left
d.rotate(-2)
print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
在这里，调用后d.rotate(-2)，前两个元素被移动到双端队列的末尾。
The rotate()操作的时间复杂度为 O(k)，其中 k 是步骤数。
使用 Deque 作为堆栈
堆栈是一种 LIFO（后进先出）数据结构。在Python中，可以使用双端队列来实现堆栈。
操作方法如下：
from collections import deque
stack = deque()
# Add elements to the stack
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)
# Remove elements from the stack
top = stack.pop()
print(top)
print(stack)
Output:
deque(['a', 'b', 'c'])
'c'
deque(['a', 'b'])
在上面的代码中，我们首先创建一个空的双端队列stack。然后我们使用以下命令将三个元素添加到堆栈中append()方法，它将元素添加到双端队列的右端。
要从堆栈中删除元素，我们使用pop()方法，删除并返回最右边的元素。
因此，遵循 LIFO 原则，最后添加的元素是第一个被删除的元素。
使用 Deque 作为队列
队列是一种 FIFO（先进先出）数据结构。您可以使用双端队列来实现队列。
就是这样：
from collections import deque
queue = deque()
# Add elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')
print(queue)
# Remove elements from the queue
front = queue.popleft()
print(front)
print(queue)
Output:
deque(['a', 'b', 'c'])
'a'
deque(['b', 'c'])
在上面的代码中，我们首先创建一个空的双端队列queue。然后我们使用以下命令将三个元素添加到队列中append() method.
要从队列中删除元素，我们使用popleft()方法，删除并返回最左边的元素。
因此，遵循 FIFO 原则，第一个添加的元素是第一个被删除的元素。
使用 Deque 作为循环队列
循环队列，也称为环形缓冲区，是最后一个元素指向第一个元素形成循环链接的队列。
Python中的Deque可以用来实现循环队列，方法是使用rotate()功能。就是这样：
from collections import deque
circular_queue = deque(['a', 'b', 'c', 'd', 'e'], maxlen=5)
# Rotate the queue to the right
circular_queue.rotate(1)
print(circular_queue)
Output:
deque(['e', 'a', 'b', 'c', 'd'], maxlen=5)
在上面的代码中，我们首先创建一个双端队列circular_queue有五个元素和一个maxlen of 5.
然后我们使用以下方法将双端队列向右旋转一步rotate(1).
最后一个元素“e”被移动到双端队列的前面，使其像循环队列一样。
嵌套双端队列
与列表类似，双端队列也可以包含其他双端队列（或列表）作为元素。这称为嵌套。
这是一个例子：
from collections import deque
# Initialize a deque with another deque as an element
d = deque(['a', deque(['b', 'c', 'd']), 'e'])
print(d)
Output:
deque(['a', deque(['b', 'c', 'd']), 'e'])
在上面的代码中，我们创建了一个双端队列d具有三个要素。
第二个元素是另一个具有三个元素的双端队列。输出显示双端队列中的双端队列。
请记住，当您修改嵌套双端队列时，更改也会反映在外部双端队列中。
了解双端队列中的线程安全
双端队列操作（append()、appendleft()、pop()、popleft() 等）在 Python 中是线程安全的。
这使得 deque 在实现需要处理并发操作的数据结构时成为合适的选择。
这是一个简单的例子：
from collections import deque
from threading import Thread
# This function appends 100000 elements to the deque
def append_elements(d):
for i in range(100000):
d.append(i)
d = deque()
# Create two threads that execute the same function
t1 = Thread(target=append_elements, args=(d,))
t2 = Thread(target=append_elements, args=(d,))
# Start the threads
t1.start()
t2.start()
# Wait for both threads to finish
t1.join()
t2.join()
print(len(d))
Output:
200000
在这段代码中，我们定义了一个函数append_elements()向双端队列添加 100000 个元素。然后我们创建两个并发执行该函数的线程。
由于双端队列操作是线程安全的，因此我们不需要担心由于同时访问和修改双端队列而可能发生的任何竞争条件。
双端队列与列表（性能比较）
双端队列和列表具有不同的性能特征，了解这些差异可以帮助您为您的用例选择正确的数据结构。
对于涉及的操作追加或弹出元素在末尾（双端队列的任一端，列表的右端），双端队列更高效比列表。
这是因为这些操作对于双端队列来说时间复杂度为 O(1)。
from collections import deque
from timeit import timeit
# A large number of elements
N = 10**6
lst = [0] * N
deq = deque(lst)
# Measure the time taken to append and pop elements at the ends
list_time = timeit(lambda: lst.append(10) or lst.pop(), number=N)
deque_time = timeit(lambda: deq.append(10) or deq.pop(), number=N)
print(f"List time: {list_time}")
print(f"Deque time: {deque_time}")
Output:
List time: 0.2596190000003844
Deque time: 0.20638569999937317
在此代码中，我们首先创建一个列表和一个包含大量元素的双端队列。
然后我们测量两种数据结构末尾追加和弹出元素所需的时间。你会发现双端队列更快。
另一方面，对于涉及的操作访问或修改中间的元素，列表比双端队列效率高得多.
这是因为 Python 中的列表是作为动态数组实现的，它提供了快速的 O(1) 随机访问。
list_time = timeit(lambda: lst[N//2] or lst.insert(N//2, 10), number=N)
deque_time = timeit(lambda: deq[N//2] or deq.insert(N//2, 10), number=N)
print(f"List time: {list_time}")
print(f"Deque time: {deque_time}")
Output:
List time: 0.1969280000012077
Deque time: 50.14866749999965
在此代码中，我们测量访问和修改两个数据结构中间的元素所需的时间。您会发现该列表明显更快。
双端队列与列表的内存消耗
除了时间复杂度之外，在双端队列和列表之间进行选择时要考虑的另一个重要因素是内存消耗。
双端队列被实现为双向链表，这意味着它们需要为每个项目存储两个指针（下一个和上一个）。
与列表相比，这会导致更高的内存开销。
让我们看一个简单的比较sys用于测量具有相同元素的列表和双端队列的大小的模块：
import sys
from collections import deque
# Create a list and a deque with 1 million elements
lst = [0] * 10**6
deq = deque(lst)
list_size = sys.getsizeof(lst)
deque_size = sys.getsizeof(deq)
print(f"List size: {list_size} bytes")
print(f"Deque size: {deque_size} bytes")
Output:
List size: 8000056 bytes
Deque size: 8250624 bytes
The 双端队列的大小比列表的大小大.
双端队列的额外内存开销是其在某些场景下的灵活性和性能优势的权衡（例如两端的高效追加/弹出）。
双端队列使用中的常见错误和陷阱
使用双端队列时，了解一些可能导致错误或意外行为的常见错误和陷阱非常重要。
过度弹出双端队列
当你从一个空的双端队列中弹出时，Python 会引发一个IndexError。在尝试弹出之前，请始终确保双端队列有元素。
from collections import deque
d = deque()
try:
d.pop()
except IndexError:
print("Cannot pop from an empty deque.")
Output:
Cannot pop from an empty deque.
忽略 Maxlen 参数
如果您指定一个maxlen创建双端队列时，当双端队列已满时，添加新元素会丢弃对端的元素。
如果您不希望元素被自动丢弃，请不要设置maxlen.
from collections import deque
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)
print(d) # Output: deque([2, 3, 4], maxlen=3)
在此代码中，当我们将元素 4 附加到已满的双端队列时，元素 1 会被自动丢弃以腾出空间。
何时使用双端队列与列表
了解何时使用双端队列与其他数据结构是编写高效代码的关键。
-
Deque：当您需要高效地从末端添加或删除项目时，例如在实现队列、堆栈或循环队列时，请使用双端队列。双端队列也是维护元素“滑动窗口”的不错选择，这要归功于
maxlen范围。
-
List：当您需要通过索引访问或修改项目时，请使用列表，因为列表为这些操作提供了 O(1) 时间复杂度。列表消耗的内存也比双端队列少。
最后，数据结构的选择在很大程度上取决于应用程序的具体要求。
双端队列的实际应用
双端队列数据结构非常通用，在许多实际应用中都有用处。
-
撤消操作：许多应用程序提供了撤消功能，可以使用双端队列来实现。每个操作都会添加到双端队列中，当用户请求撤消时，将从双端队列末尾开始的操作被取出并反转。
-
维护历史：双端队列可用于在只需要一定数量的最近记录的应用程序中维护历史记录。
-
调度算法：双端队列可用于实现轮循调度等调度算法，用于分时系统的设计。
请记住，当问题涉及在集合的任一端添加或删除元素时，请考虑使用双端队列。
关于 Python 双端队列的教程到此结束。我希望这些信息对您有用，并加深您对 Python 中的双端队列以及何时使用它们的理解。
资源
https://docs.python.org/3/library/collections.html#collections.deque
