A deque (a generalisation of the queue and the stack) adds and removes at both ends in O(1). In this lesson we look at its Python features, the monotonic queue that finds a sliding window maximum in O(n), a palindrome check, and 0-1 BFS.
Deque operations
collections.deque (collections) performs append, appendleft, pop and popleft in O(1). The index d[i] in the middle is O(n), since a deque is a chain of blocks. The difference from list: adding and removing at the front is O(n) there (table).
from collections import deque
d = deque([2, 3])
d.append(4)
d.appendleft(1)
print(d, d[0], d[-1])
print(d.pop(), d.popleft(), len(d))
d.extend([7, 8])
d.extendleft([0, -1])
print(d)deque([1, 2, 3, 4]) 1 4
4 1 2
deque([-1, 0, 2, 3, 7, 8])