deque（队列）–双向队列对象
Deque队列是由栈或者queue队列生成的。列表也可以用作队列，其中先添加的元素被最先取出 (“先进先出”)；普通列表的一个巨大缺陷在于，其往开头（左边）插入或弹出元素时显得十分慢 ，因为所有的其他元素都必须移动一位。
Deque队列和list自带的方法类似，或者说功能上是近乎一样的，它可以向内存高效添加(append)和弹出(pop)，从两端都可以。然而相比于普通列表，deque队列两个方向的大概开销都是 O(1) 复杂度。
由于collections是内建模块，无需单独安装。可以直接从collections 中导入deque：
from collections import deque
创建该对象时需要从Python自带的collections模块中进行导入deque类。它返回一个新的双向队列对象，从左到右初始化(用方法 append()) ，从 iterable （迭代对象) 数据创建。如果 iterable 没有指定，新队列为空。
接下来各位可能看一眼就觉得熟悉了，它们中的很多都已经在列表的基本方法中详细讨论并举例说明过。
接下来我们通过实例来讲解Deque队列的相关方法及其用法：
– 增 –
append(x) - 添加 x 到右端。
【eg】
from collections import deque a = deque([1,2,3,4,5,6,7]) a.append('1') a
[Out]:
deque([1, 2, 3, 4, 5, 6, 7, '1'])
其中，不仅可以将列表、元组传入deque队列，甚至可以是字符串等等，如：
【eg】
from collections import deque a = deque('abcde') a.append('1') a
[Out]:
deque(['a', 'b', 'c', 'd', 'e', '1'])
appendleft(x) - 添加 x 到左端。
【eg】
from collections import deque a = deque('abcde') a.appendleft('A') a
[Out]:
deque(['A', 'a', 'b', 'c', 'd', 'e'])
extend(iterable) - 扩展deque的右侧，通过添加iterable参数中的元素。
【eg】
from collections import deque a = deque('abcde') a.extend('ABC') a
[Out]:
deque(['a', 'b', 'c', 'd', 'e', 'A', 'B', 'C'])
【eg】
from collections import deque a = deque('abcde') a.extend(['*',6,'&',9,'^']) a
[Out]:
deque(['a', 'b', 'c', 'd', 'e', '*', 6, '&', 9, '^'])
extendleft(iterable) - 扩展deque的左侧，通过添加iterable参数中的元素。
- 左添加时，在结果中iterable参数中的顺序将被反过来添加。
【eg】
from collections import deque a = deque('abcde') a.extendleft(['*',6,'&',9,'^']) a
[Out]: deque([’^’, 9, ‘&’, 6, ‘*’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’])
insert(i, x) - 在位置 i 插入 x 。
- 如果插入会导致一个限长 deque 超出长度 maxlen 的话，就引发一个 IndexError。
【eg】
from collections import deque a = deque('abcde') a.insert(2,'666') a
[Out]:
deque(['a', 'b', '666', 'c', 'd', 'e'])
– 删 –
pop() - 移去并且返回一个元素，deque 最右侧的那一个。
- 如果没有元素的话，就引发一个 IndexError。
【eg】
from collections import deque a = deque('abcde') a.pop() a
[Out]: deque([‘a’, ‘b’, ‘c’, ‘d’])
popleft() - 移去并且返回一个元素，deque 最左侧的那一个。
- 如果没有元素的话，就引发 IndexError。
【eg】
from collections import deque a = deque('abcde') a.popleft() a
[Out]: deque([‘b’, ‘c’, ‘d’, ‘e’])
remove(value) - 移除找到的第一个 value。
- 如果没有的话就引发 ValueError。
【eg】
from collections import deque a = deque('albc3d9wea9e') a.remove('9') a
[Out]: deque([‘a’, ‘l’, ‘b’, ‘c’, ‘3’, ‘d’, ‘w’, ‘e’, ‘a’, ‘9’, ‘e’])
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.remove('9') a
[Out]: deque([1, 2, ‘W’, 3, ‘#’, 9, 6, ‘9’, 5])
clear() - 移除所有元素，使其长度为0.
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.clear() a
[Out]: deque([])
– 改 –
rotate(n=1) - 向右循环移动 n 步。
- 如果 n 是负数，就向左循环。
- 如果deque不是空的，向右循环移动一步就等价于 d.appendleft(d.pop()) ， 向左循环一步就等价于 d.append(d.popleft()) 。
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.rotate() a
[Out]: deque([5, 1, 2, ‘W’, 3, ‘9’, ‘#’, 9, 6, ‘9’])
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.rotate(1) a
[Out]: deque([5, 1, 2, ‘W’, 3, ‘9’, ‘#’, 9, 6, ‘9’])
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.rotate(2) a
[Out]: deque([‘9’, 5, 1, 2, ‘W’, 3, ‘9’, ‘#’, 9, 6])
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.rotate(-1) a
[Out]: deque([2, ‘W’, 3, ‘9’, ‘#’, 9, 6, ‘9’, 5, 1])
– 查 –
index(x[, start[, stop]]) - 返回 x 在 deque 中的位置（由值反查索引）。
- 可选参数start与stop指定了查询范围在索引 start 之后，索引 stop 之前。
- 返回第一个匹配项，如果未找到则引发 ValueError。
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.index('#',0,3)
[Out]:
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-101-453fb381b6f0> in <module> 1 from collections import deque 2 a = deque([1,2,'W',3,'9','#',9,6,'9',5]) ----> 3 a.index('#',0,3) ValueError: '#' is not in deque
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.index('#',0,6)
[Out]: 5
Deque对象还提供了一个只读属性:
maxlen - Deque的最大尺寸。
- 若没有限定则为 None 。
– 统计与排序–
count(x) - 计算 deque 中元素等于 x 的个数。
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.count('9')
[Out]: 2
reverse() - 将deque逆序排列。
- 返回 None 。
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) a.reverse() a
[Out]: deque([5, ‘9’, 6, 9, ‘#’, ‘9’, 3, ‘W’, 2, 1])
– 浅拷贝–
[注]：(点击超链接查看相关知识点)
copy() - 创建一份浅拷贝。
【eg】
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) b = a.copy() b[2] = '666' print(a,'\n',b)
[Out]: deque([1, 2, ‘W’, 3, ‘9’, ‘#’, 9, 6, ‘9’, 5])
deque([1, 2, ‘666’, 3, ‘9’, ‘#’, 9, 6, ‘9’, 5])
但要注意，Python变量的赋值是指针的复制，如果变量a直接赋值到b，则改变b也会改变a的值，因为他们修改了同一块内存空间：
from collections import deque a = deque([1,2,'W',3,'9','#',9,6,'9',5]) b = a b[2] = '666' print(a,'\n',b)
[Out]:deque([1, 2, ‘666’, 3, ‘9’, ‘#’, 9, 6, ‘9’, 5])deque([1, 2, ‘666’, 3, ‘9’, ‘#’, 9, 6, ‘9’, 5])
除了以上操作，deque 还支持迭代、封存、len(d)、reversed(d)、copy.copy(d)、copy.deepcopy(d)、成员检测运算符 in 以及下标引用例如通过 d[0] 访问首个元素等。 索引访问在两端的复杂度均为 O(1) 但在中间则会低至 O(n)。 如需快速随机访问，请改用列表。 Deque从版本3.5开始支持 __add__(), __mul__(), 和 __imul__() 。
