Модуль 21 ⏱ ~16 мин чтения 📐 1 Mermaid диаграмм

3. Implement Queue using Stacks

«Сложное поведение часто рождается из гармоничного сочетания двух простых механизмов».
— Никлаус Вирт

Синтетика с глубоким смыслом

Задача Implement Queue using Stacks (LeetCode 232) на первый взгляд кажется кандидатам странной и оторванной от реальности: «Зачем в реальном бэкенде эмулировать FIFO-очередь через два LIFO-стека, если можно написать эффективный кольцевой буфер на десяток строк?»

Ответ прост: в промышленном коде вы вряд ли напишете такую конструкцию, но на технических собеседованиях в FAANG, Yandex, Avito и VK эта задача — постоянный гость. Она мгновенно тестирует три критически важных навыка инженера:

  1. Понимание структурных инвариантов: как трансформировать обратный порядок LIFO в прямой порядок FIFO.
  2. Управление состоянием: координация данных между двумя независимыми хранилищами без гонок и лишних копирований.
  3. Глубокое понимание амортизированного анализа (Amortized Complexity): почему редкая «тяжелая» операция не делает весь алгоритм медленным.

Архитектура решения: Инверсия порядка через двойной стек

Стек разворачивает последовательность данных задом наперед. Если мы отправим в стек числа [1, 2, 3], то при последовательном извлечении получим [3, 2, 1].

Как восстановить исходный порядок [1, 2, 3] без использования сторонних коллекций?
Вспомним базовый закон логики: двойное отрицание дает утверждение. Если развернуть уже развернутую последовательность второй раз, мы получим первоначальный FIFO-порядок!

Для этого разделим обязанности между двумя стеками:

  1. Inbox (Входной стек): служит накопителем для всех новых поступлений. Метод Push(x) всегда отправляет элемент на вершину inbox за честное и строгое $O(1)$.
  2. Outbox (Выходной стек): предназначен исключительно для отдачи элементов. Методы Pop() и Peek() всегда читают с вершины outbox.
flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    subgraph OperationPush["Операция Push(x)"]
        InVal["Новый элемент x"]:::entry -->|"Всегда пишем в Inbox"| InboxStack["Стек Inbox<br>(LIFO: новейшие сверху)"]:::process
    end

    subgraph OperationPop["Операция Pop() / Peek()"]
        CheckOut{"Outbox пуст?"}:::warning
        CheckOut -->|"Да: ленивый перенос"| Transfer["Поочередно достаем из Inbox<br>и кладем в Outbox"]:::accent
        Transfer --> OutboxFilled["Стек Outbox<br>(FIFO: старейшие сверху!)"]:::process
        CheckOut -->|"Нет: данные готовы"| OutboxFilled
        OutboxFilled -->|"Снятие вершины"| Result["Самый старый элемент"]:::success
    end

Идиоматичная реализация на Go

В Go роль стека идеально выполняет обычный срез (slice). Структура получается максимально компактной и лаконичной:

Go 
package queue

// MyQueue реализует FIFO-очередь поверх двух стеков (слайсов).
type MyQueue struct {
    inbox  []int // Стек для входящих элементов
    outbox []int // Стек для выдачи элементов
}

// Constructor инициализирует пустую очередь.
func Constructor() MyQueue {
    return MyQueue{
        inbox:  make([]int, 0, 8),
        outbox: make([]int, 0, 8),
    }
}

// Push добавляет элемент x в конец очереди за O(1).
func (q *MyQueue) Push(x int) {
    q.inbox = append(q.inbox, x)
}

// moveInboxToOutbox переносит элементы из inbox в outbox при необходимости.
// Ключевой инвариант: перенос происходит ТОЛЬКО когда outbox полностью пуст!
func (q *MyQueue) moveInboxToOutbox() {
    if len(q.outbox) > 0 {
        return
    }

    // Переливаем элементы: вершина inbox становится дном outbox,
    // а дно inbox (самый старый элемент) оказывается на вершине outbox.
    for len(q.inbox) > 0 {
        n := len(q.inbox) - 1
        val := q.inbox[n]
        q.inbox = q.inbox[:n] // Снимаем с вершины inbox
        q.outbox = append(q.outbox, val)
    }
}

// Pop извлекает и возвращает элемент из начала очереди.
func (q *MyQueue) Pop() int {
    q.moveInboxToOutbox()

    if len(q.outbox) == 0 {
        return 0 // По условиям LeetCode очередь не пуста
    }

    n := len(q.outbox) - 1
    val := q.outbox[n]
    q.outbox = q.outbox[:n] // Удаляем вершину outbox
    return val
}

// Peek возвращает элемент из начала очереди без его удаления.
func (q *MyQueue) Peek() int {
    q.moveInboxToOutbox()

    if len(q.outbox) == 0 {
        return 0
    }

    return q.outbox[len(q.outbox)-1]
}

// Empty проверяет, пуста ли очередь.
func (q *MyQueue) Empty() bool {
    return len(q.inbox) == 0 && len(q.outbox) == 0
}

Взгляд под капот: Амортизированная сложность $O(1)$

На собеседовании интервьюер обязательно спросит:
«Какова временная сложность метода Pop()?»

Если кандидат ответит $O(1)$, интервьюер укажет на цикл переливания for len(q.inbox) > 0. Если кандидат ответит $O(N)$, интервьюер усомнится в понимании алгоритмов.
Правильный ответ: Худший случай (Worst Case) — $O(N)$, но Амортизированное время (Amortized Time) — строго $O(1)$.

Математическое обоснование методом учетных стоимостей (Accounting Method):

Проследим весь жизненный путь каждого отдельного элемента $x$, прошедшего через нашу очередь:

  1. Шаг 1: Вызов Push(x) помещает его в inbox — ровно 1 операция.
  2. Шаг 2: Во время редкого переноса элемент один раз снимается из inbox — ровно 1 операция.
  3. Шаг 3: Элемент добавляется в outbox — ровно 1 операция.
  4. Шаг 4: При вызове Pop() элемент снимается с вершины outbox — ровно 1 операция.

Каждый элемент за всю свою жизнь в структуре данных участвует ровно в 4 операциях перемещения, независимо от того, сколько тысяч элементов находится в очереди.
Если перенос 1000 элементов из inbox в outbox потребовал 1000 итераций, то последующие 999 вызовов Pop() выполнятся за мгновенное прямое чтение вершины за $O(1)$. Размазанная по времени стоимость каждой операции составляет $4 / 1 = O(1)$.

Итог

Задача «Очередь на двух стеках» — это классический триумф амортизированного анализа над наивной оценкой худшего случая. Ленивый перенос данных превращает потенциально дорогостоящую операцию в незаметную константу.

Освоив координацию дискретных структур, перейдем к фундаментальной задаче потоковой аналитики реального времени: вычислению бегущих метрик над бесконечным потоком данных в статье 4. Moving Average from Data Stream.