LeetCode Daily Challenge Series #1

Постановка задачи

Реализуйте стек «последний-первый-выход» (LIFO), используя только две очереди. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Решение

Прежде чем приступить к реализации кода, давайте подумаем, как действовать дальше. Есть 2 способа решения этой задачи:

• #### Использование 2 очередей: Мы можем использовать 2 очереди для реализации стека. Мы можем обработать это двумя способами —
  1. Сделать метод push дорогим
  2. Сделать метод pop дорогим

Решение зависит от приложения. В нашем случае подойдет любой из вариантов.

Дорогой метод Push:

Заталкиваем элемент в очередь2, в то время как остальные элементы хранятся в очереди1. После этого выньте элементы из Queue1 и затолкайте в Queue2. Поменяйте местами имена Queue1 и Queue2.
Если повторять этот процесс каждый раз, когда добавляется новый элемент, то элементы будут располагаться в том порядке, в котором мы ожидаем получить их из стека. Таким образом, мы получили наш стек.

Затратный метод Pop:

Каждый раз, когда нам нужно выгрузить — Выгрузите все элементы из очереди1, кроме последнего элемента, и выгрузите их в очередь2. Удалите последний элемент из очереди1 и сохраните его (это результат, который мы вернем). Поменяйте местами имена Queue1 и Queue2. Верните сохраненный элемент. Таким образом, мы получим порядок LIFO при выделении.

• #### Использование 1 очереди: Можно добиться описанного выше поведения, используя только 1 очередь.
  1. Возьмем длину очереди, скажем n.
  2. Зарегистрировать элемент
  3. Выполните цикл до тех пор, пока n. Удалите элемент из очереди и добавьте его в очередь. Это сделает новый элемент первым элементом в очереди. Если мы будем продолжать выполнять эти действия каждый раз, когда вводим новый элемент в очередь, мы получим элементы в правильном порядке, как мы ожидаем от очереди.
  4. Поскольку мы исправили порядок элементов в очереди, операция pop должна быть такой же простой, как dequeue и возврат элемента.

Код

Вот python-реализация класса для работы со стеком с помощью одной очереди.

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()


    def push(self, x: int) -> None:
        size = len(self.q1)
        self.q1.append(x)
        for i in range(size):
            el = self.q1.popleft()
            self.q1.append(el)

    def pop(self) -> int:
        return self.q1.popleft()


    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0

Примечание: Здесь мы используем коллекцию deque из python, но мы используем ее только как обычную очередь. Мы не использовали ни одно из двусторонних свойств deque