Python Collections之deque双向队列

deque是python的collections中的一个类

deque的对象像是一个列表，只不过可以固定这个deque对象的大小，以及列表是在队列的两端执行添加和弹出元素的操作，可以理解为，deque是一个双向的队列，

尽管你也可以手动在一个列表上实现这一的操作（比如增加、删除等等）。但是这里的队列方案会更加优雅并且运行得更快些。

一、基本概念

与常见的list使用区别如下所示

常用的接口

deque：append和popleft

Deque基本表现

优点

（1）deque受GIL管理，线程安全。list没有GIL锁，所以线程不安全。也就是说，在并发场景中，list可能会导致一致性问题，而deque不会。
（2）deque支持固定长度。当长度满了，当我们继续使用append时，它会自动弹出最早插入的数据。
（3） deque 更快

二、deque的简单使用以及它的方法

2.1 创建deque的方法

可以创建一个空的deque，也可以创建带数据的deque，这个数据，我们通过源码看，必须是一个可迭代的对象接口，列表，元组等等。

from collections import deque
 
# 创建一个空的deque
data = deque()
print(data)
print("=" * 60)
# 创建有数据的deque
data1 = deque('abcd')
print(data1)
print("=" * 60)
# 创建有数据的deque
data2 = deque([1, 2, 3, 4])
print(data2)
print("=" * 60)

运行结果

deque([])
============================================================
deque(['a', 'b', 'c', 'd'])
============================================================
deque([1, 2, 3, 4])
============================================================

2.2 创建deque时，并指定大小maxlen，即能装几个元素， 以及deque添加元素append()方法

from collections import deque
 
# 创建一个空的deque, 并指定最大的元素是3个
data = deque(maxlen=3)
data.append(1)
data.append(2)
data.append(3)
print(data)
data.append(4)
print(data)

运行结果，我们可以看到，当新的元素加入并且这个队列已满的时候，最老的元素会自动被移除掉

deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)

2.3 deque的 appendleft()方法

从deque队列的左侧添加数据，append()就是默认就尾部即右侧添加数据

from collections import deque

data = deque('123')
print(data)
print("=" * 60)
data.appendleft(0)
print(data)

运行结果

deque(['1', '2', '3'])
============================================================
deque([0, '1', '2', '3'])

2.4 deque的 clear()方法

清空deque队列，让其变成空队列

from collections import deque
data = deque('123')
print(data)
print("=" * 60)
data.clear()
print(data)

运行结果

deque(['1', '2', '3'])
============================================================
deque([])

2.5 deque的 copy()方法

deque的copy方法相当于深拷贝，拷贝后的地址不相同，并且原来的值修改后，不会影响拷贝后的值。

from collections import deque
data1 = deque('123')
print(data1)
print("=" * 60)
data2 = data1.copy()
print(data2)
print("地址比较")
print("data1的地址", id(data1))
print("data2的地址", id(data2))
print("修改数据后，看变化")
data1.append('4')
print(data1)
print("=" * 60)
print(data2)

运行结果

deque(['1', '2', '3'])
============================================================
deque(['1', '2', '3'])
地址比较
data1的地址 2672881599656
data2的地址 2672889020600
修改数据后，看变化
deque(['1', '2', '3', '4'])
============================================================
deque(['1', '2', '3'])

2.6 deque的count方法

count(value)，获取deque队列中某个元素的个数

from collections import deque
data1 = deque('123333333')
print(data1)
print("=" * 60)
count = data1.count('3')
print(count)

运行结果

deque(['1', '2', '3', '3', '3', '3', '3', '3', '3'])
============================================================
7

2.7 deque中的extend()方法

两个队列合并，extend(value), value的值可以是deque对象也可以是可迭代的对象，字符串，列表，元组等等

from collections import deque
data1 = deque('123')
data2 = deque('456')
data1.extend(data2)
print(data1)

运行结果

deque(['1', '2', '3', '4', '5', '6'])

2.8 deque中的extendleft()方法

两个队列合并，从左侧合并，extendleft(value), value的值可以是deque对象也可以是可迭代的对象，字符串，列表，元组等等

要注意。合并时候，value的值，也是反着来的，注意看下面的打印，从左侧开始往里面加

from collections import deque
data1 = deque('123')
data1.extendleft('456')
print(data1)

运行结果

deque(['6', '5', '4', '1', '2', '3'])

2.9 deque中的index方法

index(value,start=None,end=None), 怎么使用请看代码

from collections import deque
 
data1 = deque('helloword')
print(data1.index('o'))     # 有多个的话，取第一个的索引位置
print(data1.index('o', 5))  # 从第五个开始（索引从0开始）
print(data1.index('o', 5, 8))  # 从第五个开始 -- 第八个结束

运行结果

4
6
6

2.10 deque中的insert方法

insert(index,value)， 在index位置上，插入value值, 注意顺序

from collections import deque
data1 = deque('helloword')
data1.insert(0, '1')    # 在第一个位置上插入 1
data1.insert(0, '2')    # 在第一个位置上插入 2
data1.insert(0, ['123'])    # 在第一个位置上插入 列表123
print(data1)

运行结果

deque([['123'], '2', '1', 'h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'd'])

2.11 deque中的pop方法

pop() 方法弹出元素，从尾部弹出，并且返回弹出的这个元素

from collections import deque
 
data1 = deque('12345')
print(data1.pop())  # 弹出元素，从右侧即末尾弹出，并返回
print(data1.pop())  # 弹出元素，从右侧即末尾弹出，并返回
print(data1)

运行结果

5
4
deque(['1', '2', '3'])

2.12 deque中的popleft方法

popleft() 方法弹出元素，从头部弹出，并且返回弹出的这个元素

在队列两端插入或删除元素时间复杂度都是 O(1) ，而在列表的开头插入或删除元 素的时间复杂度为 O(N) 。

from collections import deque
 
data1 = deque('12345')
print(data1.popleft())  # 弹出元素，从左侧侧即头部弹出，并返回
print(data1.popleft())  # 弹出元素，从左侧侧即头部弹出，并返回
print(data1)

运行结果

1
2
deque(['3', '4', '5'])

2.13 deque中的remove方法

remove(value)方法，将deque队列某个元素进行移除

from collections import deque
 
data1 = deque('12345')
data1.remove('1')
print(data1)

运行结果

deque(['2', '3', '4', '5'])

2.14 deque中的reverse方法

reverse()方法，将deque队列进行反转

from collections import deque
 
data1 = deque('12345')
data1.reverse()
print(data1)

运行结果

deque(['5', '4', '3', '2', '1'])

2.15 deque中的rotate方法

rotate(n) , 将队列 向右旋转n步（默认n=1）。如果n为负，则向左旋转。

from collections import deque
 
data1 = deque('12345')
data1.rotate(3)
print(data1)
data1.rotate(-3)
print(data1)

运行结果

deque(['3', '4', '5', '1', '2'])
deque(['1', '2', '3', '4', '5'])