一、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)。文章来源:https://www.toymoban.com/news/detail-411987.html
使用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)文章来源地址https://www.toymoban.com/news/detail-411987.html
到了这里,关于Python:【基础语法】 deque()用法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!