Стек и очередь в Python: и почему list не всегда правильный выбор

Стек и очередь в Python: и почему list не всегда правильный выбор

Большинство питонистов используют list для всего подряд. 

Но у list есть конкретная асимптотика, и игнорировать её — значит писать медленный код.

📋 Stack (LIFO) → list

append() и pop() работают за O(1). Список оптимизирован именно для работы с концом:

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()  # → 3
stack.pop()  # → 2

А вот insert(0, x) и pop(0) — это O(n). Каждый раз сдвигается весь массив:

# Медленно — 200k итераций занимают несколько секунд
for n in range(200_000):
    numbers.insert(0, n)

# Быстро — то же количество итераций, мгновенно
for n in range(200_000):
    numbers.append(n)

🔄 Queue (FIFO) → deque

Если нужна очередь — берите collections.deque. Операции с обоих концов работают за O(1):

from collections import deque

queue = deque()
queue.append(1)    # добавить справа
queue.append(2)
queue.append(3)
queue.popleft()    # → 1 (первый вошёл — первый вышел)
queue.popleft()    # → 2

deque — это double-ended queue. Можно добавлять и удалять с обоих концов эффективно:

queue.appendleft(0)   # добавить слева — O(1)
queue.pop()            # удалить справа — O(1)
queue.popleft()        # удалить слева — O(1)

Правило одной строкой

Нужен стек → list. Нужна очередь → deque. Использовать list как очередь через pop(0) — это O(n) на каждую операцию.