🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Стек и очередь в 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) на каждую операцию.
📍 Навигация: Вакансии • Задачи • Собесы
Библиотека питониста
#буст