Дек (обобщение очереди и стека) позволяет добавлять и убирать элементы с обоих концов за O(1). В этом уроке разберём его возможности в Python, монотонную очередь для максимума скользящего окна за O(n), проверку палиндрома и 0-1 BFS.
Операции дека
collections.deque (collections) выполняет append, appendleft, pop, popleft за O(1). Индекс d[i] в середине — O(n), потому что дек устроен как цепочка блоков. Отличие от list: добавление и удаление в начале там O(n) (таблица).
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])