Взаимная имитация стека и очереди

Реализация очереди с помощью двух стеков и стека с помощью двух очередей — классические задачи на проектирование на собеседованиях. Они проверяют понимание инвариантных условий обеих структур и способность сохранять гарантию одной структуры, используя базовые операции другой. Кроме того, с их помощью часто переходят к обсуждению амортизированной сложности.

Главная идея такова: стеки работают по принципу LIFO, а очереди — по принципу FIFO. Чтобы преобразовать одну структуру в другую, необходимо изменить порядок элементов, а перенос элементов из одного стека в другой восстанавливает исходный порядок добавления, то есть порядок FIFO.

Ленивый подход: используйте стек inbox для операций добавления и стек outbox для операций извлечения. Когда требуется извлечь элемент из очереди, проверьте, пуст ли outbox. Если он пуст, перенесите все элементы из inbox в outbox — это изменение порядка восстанавливает порядок FIFO. Если outbox не пуст, извлеките элемент непосредственно из него. Перенос выполняется лениво, поэтому стоимость операции за O(n) амортизируется на множестве операций.

Каждый элемент переносится из inbox в outbox не более одного раза. Извлечение из outbox выполняется за O(1), а переносы происходят только тогда, когда outbox пуст. Поэтому общее количество операций для n добавлений и n извлечений составляет не более 2n операций со стеком — всего O(n), то есть амортизированно O(1) на операцию. Это означает, что в худшем случае отдельные операции могут занимать O(n), но в среднем стоимость операции равна O(1).

Реализовать стек с помощью двух очередей сложнее, поскольку очереди работают по принципу FIFO. При ленивом извлечении используются одна основная и одна временная очередь. При выполнении push добавьте элемент в основную очередь (O(1)). При выполнении pop или peek извлеките все элементы, кроме последнего, во временную очередь, сохраните последний элемент, а затем поменяйте очереди местами. Это занимает O(n) на каждое извлечение, но O(1) на каждое добавление.

Элегантная реализация с одной очередью: при выполнении push добавьте новый элемент, а затем перестройте очередь так, чтобы новый элемент оказался в начале. Для этого извлеките и снова добавьте в очередь все элементы, которые находились в ней до операции добавления. После этого операции pop и peek выполняются за O(1) (достаточно извлечь элемент или посмотреть на первый). Операция push занимает O(n) — это противоположный компромисс по сравнению с вариантом с двумя очередями.

Для очереди из двух стеков: добавление за O(1), извлечение и peek — амортизированно за O(1); выбирайте этот вариант, когда операции извлечения выполняются часто. Для стека из двух очередей: добавление за O(1), извлечение за O(n); выбирайте его, когда добавления выполняются намного чаще извлечений. Для стека из одной очереди: добавление за O(n), извлечение за O(1); выбирайте его, когда преобладают операции извлечения. На собеседовании явно проговаривайте эти компромиссы, чтобы показать, что вы думаете не только о том, «работает ли решение».

Когда элементы 1, 2, 3 добавляются в стек (inbox), снизу вверх они располагаются в порядке 1, 2, 3. Если извлечь их все и поместить во второй стек (outbox), порядок изменится на обратный: в outbox снизу будет 3, а сверху — 1. Извлечение из outbox вернёт сначала 1, затем 2, затем 3 — в точности исходный порядок добавления FIFO. Поэтому именно два изменения порядка (два стека) восстанавливают FIFO, тогда как один стек даёт LIFO.

LeetCode 232 — это классическая задача на реализацию очереди с помощью двух стеков. Ожидаемое решение использует ленивый перенос из входного стека в выходной. На собеседовании скажите, что каждый элемент перемещается из одного стека в другой не более одного раза, поэтому все операции имеют амортизированную сложность O(1). Упомяните, что отдельный вызов pop в худшем случае может занимать O(n), когда выходной стек пуст, но средняя сложность за n операций равна O(1).

LeetCode 225 — это задача на реализацию стека с помощью очередей. Самым ясным является решение с одной очередью и поворотом при добавлении. После добавления элемента x поверните очередь, переместив все элементы, которые уже находились в ней, за x. Это занимает O(n) на каждое добавление, но делает операции top и pop выполняемыми за O(1). Обозначьте этот компромисс и подтвердите, что он соответствует ограничениям, например нагрузке с редкими push или частыми pop.

Связанная задача проектирования: реализуйте три стека с использованием одного массива. Один подход делит массив на три равные фиксированные области. Более гибкий подход использует чередующееся хранение с указателями: каждый стек растёт в своей области, а при столкновении границ данные копируются. Это проверяет навыки управления динамическими массивами и встречается на собеседованиях на позицию старшего разработчика. Подход с фиксированными областями проще, но тратит место впустую, если стеки растут неравномерно.

Задачи на взаимную имитацию учат более общему принципу: любую структуру данных можно построить на основе другой, если использовать достаточный промежуточный буфер и разворот. Стоимость имитации зависит от того, какие операции Вы оптимизируете: всегда можно сделать добавление в стек за O(1) или извлечение из стека за O(1), но для выполнения обеих операций за O(1) нужна амортизация или несколько вспомогательных структур.

На собеседовании всегда спрашивайте: «Какие операции выполняются чаще?» Это помогает выбрать вариант реализации и показывает умение мыслить на уровне требований к операциям.

Проверьте, насколько Вы поняли концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

В этом уроке Вы узнали: очередь из двух стеков обеспечивает амортизированное извлечение за O(1), лениво перенося элементы из входного стека в выходной, стек из одной очереди обеспечивает извлечение за O(1), поворачивая очередь при каждом добавлении (добавление за O(n)), и выбор операции, для которой следует обеспечить O(1), зависит от характера использования. Далее мы рассмотрим внутреннее устройство хеш-таблиц и обработку коллизий.