Очередь и стек — это довольно простые структуры данных, которые мы используем в ежедневном программировании. На самом деле их можно считать простейшими структурами для хранения данных.

На протяжении всей статьи я буду использовать DS для обозначения структуры данных.

Очередь — это DS, работающая по принципу FIFO. Данным, которые приходят первыми, разрешается выходить первыми. Существует множество способов реализации очередей. Мы можем свободно использовать массивы, связанные списки и многое другое. Но здесь я собираюсь обсудить реализацию Queue с использованием другого DS под названием Stack.

Все мы знаем, что Stack — это DS, работающая по принципу LIFO. Я всегда думаю о том, чтобы сложить книги одну над другой, поэтому не стесняйтесь использовать эту аналогию, если она поможет вам визуализировать.

Я наткнулся на этот вопрос на сайте hackerrank, где от нас требовали реализовать Queue с использованием 2 стеков. Звучит просто, правда? Найдите минутку и подумайте, как мы сможем этого добиться.

Возможно, вы придумали какие-то решения, потому что существует множество способов сделать это. Так почему бы вам не попробовать это напрямую?

Вопрос

Теперь, для тех, кто попробовал и получил "ошибку тайм-аута" и для тех, кто не удосужился попробовать, позвольте мне объяснить вам самое простое и легкое решение этой проблемы.

Сначала посмотрите, как можно реализовать стек.

Как видите, я реализовал стек, используя список. Первоначально конструктор инициализирует пустой список. Мы помещаем данные, добавляя их в конец списка. При выталкивании, если мы не предоставим индекс, он выскакивает из конца списка. Таким образом, последний элемент, который будет вставлен, будет первым вынутым.

Теперь аналогичным образом для очереди мы инициализировали два разных стека. Один для постановки в очередь и один для удаления из очереди.

Мы используем enqueueStack, аналогичный стеку, только для помещения данных в конец списка. Но для dequeueStack мы знаем, что функция pop стека удаляет элемент из последнего, поэтому мы делаем следующее: мы переворачиваем enqueueStack и помещаем его в dequeueStack. Таким образом, первый элемент enqueueStack становится последним элементом dequeueStack, второй элемент enqueueStack становится предпоследним элементом dequeueStack и так далее. Итак, теперь, если мы используем функцию pop для dequeueStack, она удалит первый элемент, который мы отправили, таким образом, имитируя очередь.

Не волнуйтесь, если сейчас это звучит запутанно! Как только вы увидите код, вы поймете, о чем я говорю. На самом деле взгляните на это прямо сейчас!

Вы можете задаться вопросом, для чего нужны эти дополнительные проверки. Например, проверка того, пуст ли dequeueStack или нет. Если мы изначально не проверим это. Элементы enqueueStack при обращении будут помещаться в dequeueStack, и происходит то, что элемент dequeueStacks, который должен был быть первым, теперь оказывается последним. Поэтому сначала необходимо очистить dequeueStack, как показано в коде.

Аналогично этому, printFront печатает элемент, который должен находиться в начале очереди.

После этой реализации мы читаем входные данные из STDIN и выводим выходные данные в STDOUT.

Наш ввод примерно такой:

И полная основная функция:

Я постарался реализовать это как можно проще. Возможно, есть несколько других, более эффективных способов реализовать это. Один из них представлен здесь!