Очередь, построенная с использованием двух стеков

Условие

Реализуйте структуру данных очереди FIFO, используя только два экземпляра стека. Очередь должна предоставлять типичные операции:

• push(x) — добавляет элемент x в конец очереди;
• pop() — удаляет и возвращает элемент в начале очереди;
• peek() — возвращает элемент в начале без его удаления;
• empty() — возвращает True, если очередь пуста, иначе False.

class SimpleStack:
    def __init__(self):
        pass

    def push(self, value: int):
        pass

    def pop(self) -> int:
        pass

    def peek(self) -> int:
        pass

    def empty(self) -> bool:
        pass

Ответ

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

Два списка используются исключительно как стеки:

class Queue:
    def __init__(self):
        self.incoming = []
        self.outgoing = []

    def push(self, value):
        self.incoming.append(value)

    def _prepare(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

    def pop(self):
        self._prepare()
        return self.outgoing.pop()

    def peek(self):
        self._prepare()
        return self.outgoing[-1]

    def empty(self):
        return not self.incoming and not self.outgoing

pop/peek пустой очереди поднимают IndexError. Каждый элемент переносится между стеками не больше одного раза, поэтому редкий O(n) перенос даёт амортизированную O(1) стоимость. Если требуются экземпляры SimpleStack, замените append/pop/[-1] соответствующими методами стека.