一、Python的deque()——双向队列

Python中的标准库collections中有一个deque，该对象与list列表相似。这里的“双向”指的是deuqe的结构使用双向链表，它提供了两端都可以操作的序列，这意味着，我们可以在序列前后都执行添加或删除。大多操作与List相同，如访问元素，求序列长度等，同样deque序列中的元素类型也不唯一。

二、基本操作

1.构建deque序列

collections.deque(seq, maxlen)

>>>q1=collections.deque()
>>>q2=collections.deque([1,2,3,4,5])
>>>q3=collections.deque("12345")
>>>q4=collections.deque(range(1,6))
deque([])
deque([1, 2, 3, 4, 5])
deque(['1', '2', '3', '4', '5'])
deque([1, 2, 3, 4, 5])
2.增添元素
(1) 队头添加元素
appendleft()
>>>q=collections.deque([1,2,3,4,5])
>>>q.appendletf(0)
deque([0, 1, 2, 3, 4, 5])
(2) 队尾添加元素
append()
>>>q=collections.deque([1,2,3,4,5])
>>>q.append(0)
deque([1, 2, 3, 4, 5, 0])
(3) 限制长度的deque增加元素
>>>q=collections.deque([1,2,3,4,5], maxlen=5)
>>>q.append(0)
#超过限制长度，队尾增加，队头自动删除
deque([2, 3, 4, 5, 0], maxlen=5)
(4) 指定位置插入元素
insert(loc, elem)
loc -- 插入元素的位置
elem -- 插入的元素，可为任意类型的元素
>>>q=collections.deque([1,2,3,4,5])
>>>q.insert(2,7)
deque([1, 2, 7, 3, 4, 5])
3.删除元素
(1) 队头弹出元素
popleft()

返回弹出的元素
>>>q=collections.deque([1,2,3,4,5])
>>>q.popleft()
deque([2, 3, 4, 5])
(2) 队尾弹出元素
pop()

返回弹出的元素
>>>q=collections.deque([1,2,3,4,5])
>>>q.pop()
deque([1, 2, 3, 4])
(3) 删除指定元素
remove()
>>>q=collections.deque([1,2,3,4,5])
>>>q.remove(2)
deque([1, 3, 4, 5])
4.添加序列
(1) 队头添加序列
extendleft(seq)
seq -- 可迭代对象
>>>q1=collections.deque([1,2,3,4,5])
>>>q2=collections.deque([1,2,3,4,5])
>>>q1.extendleft([6,7,8])
>>>q2.extendleft(range(6,10))
deque([6, 7, 8, 1, 2, 3, 4, 5])
deque([9, 8, 7, 6, 1, 2, 3, 4, 5])
(2) 队尾添加序列
extendleft(seq)
seq -- 可迭代对象
>>>q1=collections.deque([1,2,3,4,5])
>>>q2=collections.deque([1,2,3,4,5])
>>>q1.extend([6,7,8])
>>>q2.extend(range(6,10))
deque([1, 2, 3, 4, 5, 6, 7, 8,])
deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
【deque是线程安全的，也就是说可以同时从deque集合的左边和右边进行操作而不会有影响】
>>>q=collections.deque([1,2,3,4,5])
>>>q.append(q.popleft())
deque([2, 3, 4, 5, 1])
5.其他操作
(1) 旋转
rotate(num)
num -- 从序列的第num个位置整体旋转

若num>=1，表示从右向左的num个数，与其左边的所有数顺时针旋转

若num<=-1，表示从左向右的-num个数，与其右边的所有数逆时针旋转
>>>q=collections.deque([1,2,3,4,5])
>>>q.rotate(3)
deque([3, 4, 5, 1, 2])
num=3，[3,4,5]和[1,2]进行顺时针旋转
>>>q=collections.deque([1,2,3,4,5])
>>>q.rotate(-3)
deque([4, 5, 1, 2, 3])
num=-3，[1,2,3]和[4,5]进行逆时针旋转

① |num|可以大于序列的长度，可以把队列看作是首位相连即可，如实例中num=6，等价于num%5=1，即num=1的效果，负数同理。

② num=0以及序列长度的倍数翻转没有效果，即序列不变。

③ 旋转的结果也可以通过同时popleft()和append()、pop()和appendleft()两种方式得到相同结果。但时间复杂度回变高，因此旋转更好一些。

关于旋转的应用可看例题：找出游戏的获胜者

(2) 其他
in操作符、index()查找索引位置、copy()复制一个新队列、count()统计队列中元素个数等均可使用。
三、deuqe与list的区别
相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。
使用q=deque()代替q=list()，因为q.popleft()效率比q.pop(0)高

这是因为：列表实现是基于数组的。pop(0)从列表中删除第一个项，它需要左移len(lst) - 1个项来填补空白。     deque()实现使用双向链表。因此无论deque有多大，deque.popleft()都需要一个常量的操作数。

即deque.popleft()：T(n)=O(1)，而list.pop(0)：T(n)=O(n)