deque
固定大小的队列
from collections import deque
q = deque(maxlen=3)
q.append(1)
q.append(2)
q.append(3)
print(q)
# deque([1, 2, 3], maxlen=3)
q.append(4)
print(q)
# deque([2, 3, 4], maxlen=3)
q.append(5)
print(q)
# deque([3, 4, 5], maxlen=3)
q = deque()
q.append(1)
q.append(2)
q.append(3)
print(q)
# deque([1, 2, 3])
q.appendleft(4)
print(q)
# deque([4, 1, 2, 3])
print(q.pop())
# 3
print(q)
# deque([4, 1, 2])
print(q.popleft())
# 4
无限大小的队列
在队列两端插入或删除元素时间复杂度都是 O(1) ，
而在列表的开头插入或删除元素的时间复杂度为 O(N) 。
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.append(3)
print(q)
# deque([1, 2, 3])
q.appendleft(4)
print(q)
# deque([4, 1, 2, 3])
print(q.pop())
# 3
print(q)
# deque([4, 1, 2])
print(q.popleft())
# 4