deque#
collections.deque is a double-ended queue. O(1) append and
pop at both ends. Use instead of list when popping from
the front (list.pop(0) is O(n)).
from collections import deque
q = deque()
q.append(1); q.append(2) # right
q.appendleft(0) # left
q.popleft() # O(1)
q = deque(maxlen=100) # fixed-size ring buffer
The maxlen form is a ring buffer; once full, appending one
end evicts from the other. Useful for sliding windows and recent-N
history.
recent = deque(maxlen=100)
for event in stream:
recent.append(event) # auto-evicts oldest beyond 100
deque also supports rotate(n) (positive = right, negative
= left) and extend / extendleft for bulk ops.