Как реализовать очередь на двух стеках и какова амортизированная сложность?

Входящий стек принимает `enqueue`, исходящий отдаёт `dequeue`; когда исходящий пуст, в него перекладывают все элементы входящего — порядок переворачивается и становится FIFO. Каждая операция стоит амортизированно O(1).

Реализация

class TwoStackQueue {
  #inbox = [];
  #outbox = [];

  enqueue(x) { this.#inbox.push(x); }

  dequeue() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length) this.#outbox.push(this.#inbox.pop());
    }
    return this.#outbox.pop();
  }
}

Почему амортизированно O(1)

• Каждый элемент за свою жизнь ровно один раз кладётся во входящий стек, один раз перекладывается и один раз извлекается — не больше четырёх операций со стеками.
• Отдельный dequeue в худшем случае стоит O(n), но n операций в сумме — O(n).
• Ошибка — перекладывать при каждом dequeue или возвращать элементы обратно: это даёт O(n) на операцию.

Где пригождается

• Чисто функциональные языки: очередь из двух иммутабельных списков (Окасаки).
• Очередь с минимумом за O(1): оба стека хранят пары «значение, минимум ниже по стеку» — основа задачи о минимуме в скользящем окне.

Коротко для собеседования

Пишем во входящий стек, читаем из исходящего и перекладываем элементы только тогда, когда исходящий пуст. Отдельный dequeue может стоить O(n), но каждый элемент перекладывается один раз, поэтому в среднем выходит O(1); типичная ошибка — перекладывать при каждом вызове.