Стеки, очереди и deques

Stacks моделируют last-in-first-out работу: parsing brackets, undo history, DFS и monotonic candidates. Queues моделируют first-in-first-out работу: BFS, scheduling и buffering. Deques поддерживают оба конца и встречаются в sliding window maximum и double-ended scheduling задачах.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры смотрят на access invariant: что входит, что выходит и почему структура гарантирует следующий корректный item.

Типовые ошибки: Array.shift в JavaScript может быть O(n), потому что элементы сдвигаются. Для queues в performance-sensitive примерах лучше head index или deque abstraction.

Чеклист:

• Назовите LIFO или FIFO.
• Объясните invariant.
• Выбирайте head-index queues в JS.
• Проверьте empty-pop behavior.