Python：【基础语法】 deque()用法

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

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

二、基本操作

1.构建deque序列

collections.deque(seq, maxlen)

• seq — 可迭代对象，如列表、字符串、 range() 函数等。
• maxlen — deque的限制长度
  两个参数都为可选参数。通常不设定maxlen，但注意当限制长度的deque增加超过限制数的元素时, 另一边的元素会自动删除，详见下文增加元素的操作。
  返回一个deque序列。

>>>q1=collections.deque()
>>>q2=collections.deque([1,2,3,4,5])
>>>q3=collections.deque("12345")
>>>q4=collections.deque(range(1,6))
>>>q1
>>>q2
>>>q3
>>>q4

结果为：

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)
>>>q

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

(2) 队尾添加元素

append()

>>>q=collections.deque([1,2,3,4,5])
>>>q.append(0)
>>>q

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

(3) 限制长度的deque增加元素

>>>q=collections.deque([1,2,3,4,5], maxlen=5)
>>>q.append(0)
>>>q

结果为：

#超过限制长度，队尾增加，队头自动删除
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)
>>>q

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

3.删除元素

(1) 队头弹出元素

popleft()
返回弹出的元素

>>>q=collections.deque([1,2,3,4,5])
>>>q.popleft()
>>>q

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

(2) 队尾弹出元素

pop()
返回弹出的元素

>>>q=collections.deque([1,2,3,4,5])
>>>q.pop()
>>>q

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

(3) 删除指定元素

remove()

>>>q=collections.deque([1,2,3,4,5])
>>>q.remove(2)
>>>q

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))
>>>q1
>>>q2

结果为：

deque([6, 7, 8, 1, 2, 3, 4, 5])
deque([9, 8, 7, 6, 1, 2, 3, 4, 5])

(2) 队尾添加序列

extend(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))
>>>q1
>>>q2

结果为：

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())
>>>q

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)
>>>q

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

num=3，[3,4,5]和[1,2]进行顺时针旋转

>>>q=collections.deque([1,2,3,4,5])
>>>q.rotate(-3)
>>>q

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)