Стек и очередь в Python: и почему list не всегда правильный выбор — 13 июля 2026 г. в 13:42:13.082
Стек и очередь в 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) на каждую операцию.