数据结构子目录https://www.jianshu.com/p/a344fa483655

双端队列

什么是双端队列

双端队列顾名思义就是两边都可以增删的队列。他的实现是Python自带的模块--deque模块。
deque模块，它是collections库的一部分。deque实现了双端队列，意味着你可以从队列的两端加入和删除元素。

创建

from collections import deque

# 实例化一个deque对象
d = deque()
print(d)
print(type(d))

---------
输出结果：
deque([])
<class 'collections.deque'>

增

from collections import deque

# 实例化一个deque对象
d = deque()

# 和list的操作有些类似
d.append('a')
d.append('b')
d.append('c')
print(len(d))
print(d[0])
print(d[-1])
print(d)

---------
输出结果:
3
a
c
deque(['a', 'b', 'c'])

删

from collections import deque

# 实例化一个deque对象
d = deque()

d1 = deque('abcde')
print(d1)
d1.popleft()
print(d1)
d1.pop()
print(d1)

--------
输出结果：
deque(['a', 'b', 'c', 'd', 'e'])
deque(['b', 'c', 'd', 'e'])
deque(['b', 'c', 'd'])

限制

我们也可以限制deque中元素的个数，当deque的元素数超过能存放的元素数，它会从相对一端pop元素。

from collections import deque

d = deque(maxlen=5)  # 限制元素为5

d.append(1)
d.append(2)
d.append(3)
d.append(4)
d.append(5)
print(d)
d.append(6)
d.append(7)
print(d)

--------
输出结果：
deque([1, 2, 3, 4, 5], maxlen=5)
deque([3, 4, 5, 6, 7], maxlen=5)

扩展

from collections import deque

d = deque([1, 2, 3, 4, 5])
print(d)
d.extendleft([0])
d.extend([6, 7, 8])
print(d)

------
输出结果:
deque([1, 2, 3, 4, 5])
deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

常用方法一览

append(x)：把元素x添加到队列的右端
appendleft(x)：把元素x添加到队列的左端
clear()：清空队列中所有元素
copy()：创建队列的浅拷贝
count(x)：计算队列中等于x元素的个数
extend(iterable)：在队列右端通过添加元素扩展
extendleft(iterable)：在队列左端通过添加元素扩展
index(x[, start[, stop]])：返回x元素在队列中的索引，放回第一个匹配，如果没有找到抛ValueError
insert(i, x)：在队列的i索引处，插入x元素
pop()：移除并返回deque右端的元素，如果没有元素抛IndexError
popleft()：移除并返回deque左端的元素，如果没有元素抛IndexError
remove(value)：删除第一个匹配value的元素，如果没有找到抛ValueError
reverse()：在原地反转队列中的元素
rotate(n)：把队列左端n个元素放到右端，如果为负值，右端到左端。如果n为1，等同d.appendleft(d.pop())
maxlen：只读属性，队列中的最大元素数