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）的单向队列。
如果我们只在双向队列的一端存数据和取数据，另一端不操作数据，那么就是实现了栈。