A - Как перевернуть стек

Чтобы понять, как построить очередь, используя два стека, вы должны понимать, как полностью перевернуть стек. Помните, как работает стек, это очень похоже на стек блюдо на вашей кухне. Последнее вымытое блюдо будет на вершине чистой стопки, которая называется L ast I n F irst O ut (LIFO) в области компьютерных наук.

Давайте представим наш стек как бутылку, как показано ниже:

Если мы добавим целые числа 1,2,3 соответственно, то 3 будет на вершине стека. Поскольку сначала будет помещен 1, затем 2 будет помещен на вершину 1. Наконец, 3 будет помещен на вершину стека, и последнее состояние нашего стека, представленное в виде бутылки, будет таким, как показано ниже;

Теперь наш стек представлен в виде бутылки, заполненной значениями 3,2,1. И мы хотим перевернуть стек так, чтобы верхний элемент стека был 1, а нижний элемент стека был 3. Что мы можем сделать? Мы можем взять бутылку и держать ее вверх дном, чтобы все значения перевернулись по порядку?

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

Итак, мы знаем, как перевернуть стек.

B - Использование двух стеков в качестве очереди

В предыдущей части я объяснил, как мы можем изменить порядок элементов стека. Это было важно, потому что если мы помещаем элементы в стек, и выводим их, то результат будет точно в обратном порядке очереди. Думая на примере, давайте поместим массив целых чисел {1, 2, 3, 4, 5} в стек. Если мы вытолкнем элементы и распечатаем их до тех пор, пока стек не станет пустым, мы получим массив в порядке, обратном порядку проталкивания, который будет равен {5, 4, 3, 2, 1} , выход будет {1, 2, 3, 4, 5}. Таким образом, очевидно, что для одного и того же порядка ввода элементов вывод очереди в точности противоположен выводу стека. Поскольку мы знаем, как перевернуть стек, используя дополнительный стек, мы можем построить очередь, используя два стека.

Наша модель очереди будет состоять из двух стеков. Один стек будет использоваться для операции enqueue (стек # 1 слева, будет называться Input Stack), другой стек будет использоваться для операции dequeue (стек # 2 справа, будет называться Output Стек). Посмотрите на изображение ниже:

Наш псевдокод имеет следующий вид:

Операция постановки в очередь

Push every input element to the Input Stack

Операция удаления из очереди

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and push them to the Output Stack until Input Stack is Empty

pop from Output Stack

Давайте поставим в очередь целые числа {1, 2, 3} соответственно. Целые числа будут помещены во входной стек ( стек № 1 ), который расположен слева;

[1138]

Тогда что будет, если мы выполним операцию удаления очереди? Всякий раз, когда выполняется операция удаления очереди, очередь будет проверять, является ли стек вывода пустым или нет (см. Псевдокод выше). Если стек вывода пуст, то стек вывода будет извлечен на выходе, чтобы элементы стека ввода будет полностью изменен. Перед возвратом значения состояние очереди будет таким, как показано ниже:

Проверьте порядок элементов в стеке вывода ( Стек № 2). Очевидно, что мы можем вытолкнуть элементы из стека вывода, чтобы вывод был таким же, как если бы мы вышли из очереди. Таким образом, если мы выполним две операции удаления очереди, сначала получим {1, 2} соответственно. Тогда элемент 3 будет единственным элементом выходного стека,