deque队列即双向队列，其中deque是”double-ended queue”的简写。deque支持从左边或者右边高效的添加append和弹出pop ，时间复杂度是O(1)。同时，deque也是线程安全的。

deque的创建

对于deque来说，初始化参数可以有两个，一个是iterable对象，一个maxlen值。

class collection.deque([ iterable [,maxlen ]])

如果maxlen没有指定或者是None,那么deque可以增长到任意的长度。否则，deque的最大长度就是maxlen。一旦限定长度的deque满了，当新项加入时，同样数量的项就从另一端弹出。另外，如果iterable没有指定的话，那么会创建一个空deque。

1
2
3
4
5
from collections import deque
d = deque() #创建一个空deque
d = deque("abc") # 创建一个deque含有3个items
d = deque("abc",4) # 创建一个deque含有3个items,并且其最大长度为4
d = deque(4) # 这样是不被允许的

deque的方法

下图展示了deque的一些基本操作。

双向队列dequez对象支持如下的所有方法。

  • append(x) # 将元素x添加到队列的右端。
1
2
d = deque()
d.append(1) # 将1添加到双向队列右端

  • appnedleft(x) # 将元素x添加到双向队列左端。

  • clear() # 移除所有的元素，使双向队列的长度为0。

  • copy() # 创建一个浅拷贝。注意：这是3.5版本添加的新功能。

  • extend(iterable) # 将iterable中的元素添加到双向队列的右边。

  • extendleft(iterable) # 将iterable中的元素天骄到双向队列的左边。注意：左添加时，在结果中iterable参数中的顺序将被反过来添加。

1
2
3
d.append(1)
d.extendleft([3,4,5])
#output:deque([5, 4, 3, 1])

  • index(x [,start [,stop ]]) # 返回元素x在deque中的位置，范围为索引start之后，索引stop之前。默认是整个deque。如果找到，则返回第一个匹配项，如果没有找到，则会引发一个ValueError。

  • insert(i,x) # 在位置i插入元素x。如果插入导致deque超出maxlen，那么就会引发一个indexError。注意：这是3.5版本添加的新功能。

  • pop() # 移去并返回deque最右侧的元素。如果没有的话，则会引发引发一个IndexError。注意：这是3.5版本添加的新功能。

  • popleft() # 与pop()类似，不过这次是左边。

  • remove(value) # 移除找到的第一个value。如果找不到的话，则会引起一个ValueError。

  • reverse() # 将deque逆序。返回的是一个None。注意：这是3.2版本添加的新功能。

  • rotate(n=1) # 向右循环移动n步。如果n为负数的话，则就向左循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 顺时针
q = collections.deque([1, 2, 3, 4])
q.rotate(1)
print(q)  # [4, 1, 2, 3]
q.rotate(1)
print(q)  # [3, 4, 1, 2]

# 逆时针
q = collections.deque([1, 2, 3, 4])
q.rotate(-1)
print(q)  # [2, 3, 4, 1]
q.rotate(-1)
print(q)  # [3, 4, 1, 2]

其他

除了以上操作，deque 还支持迭代、封存、len(d)、reversed(d)、copy.copy(d)、copy.deepcopy(d)、成员检测运算符 in 以及下标引用例如通过 d[0] 访问首个元素等。 索引访问在两端的复杂度时均为 O(1) 但在中间时则会低至 O(n)。 如需快速随机访问，请改用列表。

1
2
3
4
# in运算符
q = collections.deque([1, 2, 3, 4])
print(5 in q)  # False
print(1 in q)  # True

参考