Условие

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

• push(x) — вставляет элемент x в конец очереди.

• pop() — удаляет элемент из начала очереди и возвращает его.

• peek() — возвращает элемент из начала очереди, не удаляя его.

• empty() — возвращает true, если очередь пуста, и false в противном случае.

Примечания:

• Все операции должны иметь амортизированную сложность O(1).

• Использовать только стандартные операции стека: push, pop, peek/top и empty.

• Не использовать встроенные структуры данных очереди.

Решение

class MyQueue {
    private val inputStack = Stack<Int>()
    private val outputStack = Stack<Int>()

    fun push(x: Int) {
        inputStack.push(x)
    }

    fun pop(): Int {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop())
            }
        }
        return outputStack.pop()
    }

    fun peek(): Int {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop())
            }
        }
        return outputStack.peek()
    }

    fun empty(): Boolean {
        return inputStack.isEmpty() && outputStack.isEmpty()
    }
}