Дек

Дек (double-ended queue) допускает добавление и удаление элементов с обоих концов за O(1). Это обобщение стека и очереди; удобен для алгоритма «скользящее окно» и задач, где нужны оба конца.

Сложность: операции с любого конца — O(1); доступ к середине — O(n). Память: O(n).

from collections import deque
d = deque([2, 3])
d.appendleft(1)   # [1, 2, 3]
d.append(4)       # [1, 2, 3, 4]
d.pop()           # -> 4
d.popleft()       # -> 1