Python deque - 双端队列

Question

deque 是 Python 内置的双端队列（Double ended queue）实现，可以实现「两头可以进出」的数据类型。

1. 定义 deque

deque 的定义方式如下：

from collections import deque

d = deque()

2. 常用方法

2.1. append / appendleft

在队列的右端 / 左端添加元素。

d.append(1)
d.appendleft(2)
d.append(3)
print(d) # deque([2, 1, 3])

2.2. pop / popleft

从队列的右端 / 左端弹出元素。如果队列为空会抛出异常。

print(d.pop()) # 3
print(d.popleft()) # 2
print(d) # deque([1])

2.3. clear / copy

清空队列。做一个队列副本。

d.clear()
print(d) # deque([])

d2 = d.copy()

2.4. count

计算队列中某个元素的出现次数。

d.append(1)
d.append(2)
d.append(2)
print(d.count(2)) # 2

2.5. extend / extendleft

当有多个元素需要添加时，尽量使用这两个方法进行添加，这样效率最高。

d.extend([4, 5, 6])
d.extendleft([7, 8, 9])
print(d) # deque([9, 8, 7, 4, 5, 6])

2.6. index

获取队列中某个元素第一次出现的位置。

print(d.index(5)) # 4

2.7. insert

在队列中的指定位置插入元素。

d.insert(2, 10)
print(d) # deque([9, 8, 10, 7, 4, 5, 6])

2.8. remove

从队列中移除某个元素。如果该元素不存在会抛出异常。

d.remove(10)
print(d) # deque([9, 8, 7, 4, 5, 6])

2.9. reverse

反转整个队列。

d.reverse()
print(d) # deque([6, 5, 4, 7, 8, 9])

2.10. rotate

将队列左右移动指定的位置。

d.rotate(2)
print(d) # deque([8, 9, 6, 5, 4, 7])
d.rotate(-2)
print(d) # deque([6, 5, 4, 7, 8, 9])

3. deque 的优势

与直接使用列表相比， deque 有以下优势：

• 插入和删除元素更快，时间复杂度为 O(1)。
• 可以从两个方向操作数据，从而避免了在前面增加元素时的整体移动，进而使效率更高。
• 基本可以当做一个大杂烩，既可以用作队列，也可以用作栈，也可以用作双端队列，可扩展性更好。

4. 总结

deque 是 Python 常用的序列数据类型之一，是一种既可以用作队列，也可以用作栈，还可以实现双端队列的高效数据类型。如果在程序实现过程中需要大量进行多个元素的插入或删除操作，可以使用 deque 来提升性能。