大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

Python之双向队列

Python collections模块中的deque类是一种双向队列(double-ended queue,双端队列)。从该队列的头部或尾部插入或移除一个元素,时间复杂度为O(1),就是不会因数据的大小及位置等因素而变化。

而对内置的list类型,从list尾部插入或删除元素,时间复杂度也是O(1),但是从list头部插入或移除元素,时间复杂度就是O(n),这与deque相比,要慢得多。

deque 可以迭代,可以使用函数len求长度,可以用 in 操作符判断是否含有某一元素,支持通过索引获取元素;

下面是一些deque的方法:

>>> from collections import deque
>>> d = deque('ghi')
>>> d
deque(['g', 'h', 'i'])
>>> for elem in d:   # deque 可迭代
        print(elem)
# 不带 >>> 的是输出    
g
h
i

>>> d.append('j')
>>> d
deque(['g', 'h', 'i', 'j'])
>>> d.appendleft('f')
>>> d
deque(['f', 'g', 'h', 'i', 'j'])
>>> d.pop()
'j'
>>> d
deque(['f', 'g', 'h', 'i'])
>>> d.popleft()
'f'
>>> d
deque(['g', 'h', 'i'])
>>> d[0]
'g'
>>> d[-1]
'i'
>>> d.extend('jkl')  # 在右端一次增加多个元素
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
>>> d.extendleft('edf')
>>> d
deque(['f', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'l'])
>>> 'k' in d
True
>>> d.clear()
>>> d
deque([])
>>> list1 = ['a', 'b', 'c']
>>> d = deque(list1)  # 可以把一个列表转为deque
>>> d
deque(['a', 'b', 'c'])
>>> d.count('b')  # count方法可以统计duque中某一元素的个数
1
>>> deque(list1, 2)  # 只取后两个元素,可以实现打开文件时只取后面几行
deque(['b', 'c'], maxlen=2)

如果我们只在双向队列的一端取数据,另一端存数据,那么就实现了先进先出(first-in-first-out,FIFO)的单向队列。
如果我们只在双向队列的一端存数据和取数据,另一端不操作数据,那么就是实现了栈。