Почему у нас есть элементы, возвращаемые в стек 1 из стека 2

Question

Недавно я натолкнулся на алгоритм построения очереди с использованием 2 стеков, который выглядит следующим образом:

Метод 1 (Делая операцию enQueue дорогостоящей): Этот метод гарантирует, что самый старый введенный элемент всегдана вершине стека 1, так что операция deQueue просто появляется из stack1.Чтобы поместить элемент на вершину стека 1, используется стек 2.

enQueue(q, x)
  1) While stack1 is not empty, push everything from stack1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.
Here time complexity will be O(n)


deQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it
Here time complexity will be O(1)

Теперь этот алгоритм имеет смысл, за исключением третьего пункта о том, почему мы помещаем все обратно в стек 1. Почему мы не можем использовать стек 2 в качествеочередь (во время операции постановки в очередь)

Answer 1

Почему все выталкивается обратно в стек1

Это обусловлено тем фактом, что при выполнении операции удаления очереди вы извлекаете элемент из стека 1.

Предположим, у вас есть три операции нажатия x1, x2, x3 в одном и том же порядке.Поскольку ваша операция удаления из очереди всегда происходит из stack1, вы должны убедиться, что x1 находится сверху, с x2 под номером два и x3 под номером три сверху.Это может быть обеспечено только третьей точкой .

В алгоритме, о котором вы упоминали выше , очередь и очередь выполняются для стека1 .

Почему мы не можем использовать стек 2 в качестве очереди (во времяоперация постановки в очередь)

В этом случае вам придется выполнить операцию удаления очереди из стека 1.

ставить в очередь (q, x):

1. вставить в стек 2. O (1)

deQueue (q):

1. Если стек1 не пуст, тоpop из stack1.

2. Если stack1 пусто

   2.1 Если stack2 также пусто, выдать ошибку.

   2.2 Перенести все из stack2 в stack1.Теперь вытолкните вершину из stack1.Амортизированная сложность очереди будет O (1), потому что количество переданных элементов равно количеству вытолкнутых элементов из stack1.