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

Как сделать очередь из двух стеков за амортизированное O(1) и стек из очереди: код на Python и JavaScript, метод потенциалов и бухгалтерский метод, худший случай и типичные ошибки.

11 мин чтенияалгоритмы · стек · очередь · python

Коротко

ВопросОтвет
Очередь на двух стекахinbox для push, outbox для pop; переливаем, только когда outbox пуст
Сложность очередиАмортизированно O(1)O(1) на операцию, но отдельный pop может стоить O(n)O(n)
Почему амортизированноКаждый элемент перекладывается из стека в стек ровно один раз за всю жизнь
Стек на очередиПосле push прокручиваем очередь, чтобы новый элемент оказался в голове: push за O(n)O(n)
Что проверяют на интервьюУмение объяснить амортизацию: агрегатно, «монетками» или через потенциал

Задачи «очередь через стеки» (LeetCode 232) и «стек через очереди» (LeetCode 225) выглядят как разминка: никто в продакшене не собирает очередь из двух массивов. Но их любят на собеседованиях за follow-up: «а какая сложность у pop?». Правильный ответ — «амортизированно O(1)O(1)» — и дальше нужно уметь объяснить, что это значит и почему это не то же самое, что O(1)O(1) в худшем случае. Разберём обе задачи, три способа доказать оценку и места, где амортизация подводит.

Условие

Нужно реализовать очередь (FIFO) с операциями:

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

Разрешено пользоваться только стеками и только их операциями: положить на вершину, снять с вершины, посмотреть вершину, узнать размер. В Python стеком служит обычный list с append/pop, в JavaScript — массив с push/pop.

Если вы хотите освежить сами структуры, начните со статьи про стек и очередь.

Наивное решение: переливать туда и обратно

Стек отдаёт элементы в обратном порядке. Значит, чтобы добраться до самого старого элемента, который лежит на дне, нужно переложить всё во второй стек — там порядок перевернётся, и старый окажется сверху. Наивная версия забирает его и перекладывает всё обратно:

class SlowQueue: """Переливает всё туда и обратно на каждом pop — O(n) на операцию.""" def __init__(self): self.main = [] self.tmp = [] def push(self, x): self.main.append(x) def pop(self): while self.main: self.tmp.append(self.main.pop()) x = self.tmp.pop() while self.tmp: self.main.append(self.tmp.pop()) return x

Это работает, но каждый pop стоит O(n)O(n), а nn операций — O(n2)O(n^2). Лишняя работа очевидна: мы аккуратно разворачиваем элементы в правильный порядок, а потом зачем-то разворачиваем обратно.

Ключевая идея: не переливать обратно

Заведём два стека с разными ролями:

  • inbox — сюда только кладём;
  • outbox — отсюда только забираем.

Пока в outbox что-то есть, на его вершине лежит самый старый элемент очереди, и pop просто снимает его. Когда outbox опустел, переливаем в него весь inbox — порядок разворачивается, и самый старый из оставшихся снова оказывается сверху.

Почему нельзя переливать, если outbox не пуст? Потому что элементы из inbox новее любых элементов outbox. Если положить их сверху, они окажутся в очереди раньше старых — FIFO сломается.

class MyQueue: def __init__(self): self.inbox = [] # сюда кладём self.outbox = [] # отсюда забираем def push(self, x): self.inbox.append(x) def _shift(self): # переливаем, только когда outbox пуст if not self.outbox: while self.inbox: self.outbox.append(self.inbox.pop()) def pop(self): self._shift() if not self.outbox: raise IndexError('pop from empty queue') return self.outbox.pop() def peek(self): self._shift() if not self.outbox: raise IndexError('peek from empty queue') return self.outbox[-1] def empty(self): return not self.inbox and not self.outbox def __len__(self): return len(self.inbox) + len(self.outbox) q = MyQueue() for x in [1, 2, 3]: q.push(x) print(q.pop(), q.peek()) # 1 2 q.push(4) print(q.pop(), q.pop(), q.pop(), q.empty()) # 2 3 4 True

То же на JavaScript:

class MyQueue { constructor() { this.inbox = [] this.outbox = [] } push(x) { this.inbox.push(x) } #shift() { if (this.outbox.length === 0) { while (this.inbox.length > 0) this.outbox.push(this.inbox.pop()) } } pop() { this.#shift() if (this.outbox.length === 0) throw new Error('pop from empty queue') return this.outbox.pop() } peek() { this.#shift() if (this.outbox.length === 0) throw new Error('peek from empty queue') return this.outbox[this.outbox.length - 1] } empty() { return this.inbox.length === 0 && this.outbox.length === 0 } } const q = new MyQueue() q.push(1) q.push(2) console.log(q.peek()) // 1 console.log(q.pop()) // 1 q.push(3) console.log(q.pop(), q.pop(), q.empty()) // 2 3 true

Разбор на примере

Проследим состояние стеков (вершина справа):

ОперацияinboxoutboxРезультатЧто произошло
push(1)[1][]
push(2)[1, 2][]
push(3)[1,2,3][]
pop()[][3, 2]1Перелили 3 элемента, сняли 1
push(4)[4][3, 2]Новый элемент ждёт в inbox
pop()[4][3]2Без переливания
pop()[4][]3Без переливания
pop()[][]4Перелили 1 элемент, сняли 4

Первый pop сделал три перекладывания, следующие два — ни одного. Дорогие операции бывают, но редко, и каждая «оплачивает» несколько последующих дешёвых.

Амортизированный анализ

Худший случай одной операции — O(n)O(n): если положить миллион элементов и вызвать pop, он переложит миллион. Но такой pop не может повторяться подряд. Амортизированная стоимость — это средняя стоимость операции в худшей последовательности операций. Это не среднее по случайным входам: никакой вероятности здесь нет, оценка гарантирована для любой последовательности.

Докажем, что последовательность из mm операций над пустой очередью стоит O(m)O(m). Есть три стандартных способа, и на собеседовании хватит любого — но полезно знать все.

Агрегатный метод: считаем путь каждого элемента

Проследим жизнь одного элемента. За всё время он:

  1. кладётся в inbox — одна операция;
  2. снимается с inbox при переливании — одна;
  3. кладётся в outbox — одна;
  4. снимается с outbox при pop — одна.

Ни один шаг не повторяется: элемент никогда не возвращается из outbox в inbox. Значит, на элемент приходится не больше четырёх операций со стеками, а на mm операций очереди — не больше 4m4m. В среднем O(1)O(1).

Проверим это экспериментально, посчитав элементарные операции со стеками:

class CountingQueue(MyQueue): def __init__(self): super().__init__() self.ops = 0 # число push/pop по стекам def push(self, x): self.ops += 1 super().push(x) def _shift(self): if not self.outbox: self.ops += 2 * len(self.inbox) super()._shift() def pop(self): self.ops += 1 return super().pop() n = 100_000 q = CountingQueue() for i in range(n): q.push(i) if i % 3 == 0: q.pop() while not q.empty(): q.pop() print(q.ops, q.ops / (2 * n)) # 400000 2.0

nn вставок и nn извлечений — это 2n2n операций очереди и ровно 4n4n операций со стеками: по две на операцию очереди, как и предсказывает подсчёт.

Бухгалтерский метод: монетки на элементах

Будем брать за каждый push три монетки вместо одной. Одна тратится на сам push, две кладутся «на элемент» в inbox. Когда приходит время переливать, у каждого элемента в inbox уже лежат две монетки: одна оплачивает снятие с inbox, вторая — укладку в outbox. Сам pop стоит одну монетку.

Баланс никогда не уходит в минус, поэтому реальная стоимость любой последовательности не больше суммы выставленных счетов: 33 за push и 11 за pop. Обе — константы.

Метод потенциалов

Формальная версия той же идеи. Введём потенциал — функцию состояния структуры, которая неотрицательна и в начале равна нулю:

Φ=2⋅∣inbox∣\Phi = 2 \cdot |\text{inbox}|

Амортизированная стоимость операции — реальная стоимость плюс изменение потенциала: c^=c+ΔΦ\hat c = c + \Delta\Phi. Посчитаем:

  • push: c=1c = 1, потенциал растёт на 22, итого c^=3\hat c = 3;
  • pop без переливания: c=1c = 1, ΔΦ=0\Delta\Phi = 0, итого c^=1\hat c = 1;
  • pop с переливанием kk элементов: c=2k+1c = 2k + 1, потенциал падает на 2k2k, итого c^=1\hat c = 1.

Сумма амортизированных стоимостей равна сумме реальных плюс Φконец−Φначало≥0\Phi_\text{конец} - \Phi_\text{начало} \ge 0. Значит, реальная стоимость не больше 3m3m — то же O(m)O(m).

Потенциал — это «накопленная работа, которую ещё предстоит сделать»: элементы в inbox рано или поздно придётся переложить. Тот же приём объясняет, почему динамический массив добавляет элемент за амортизированное O(1)O(1), несмотря на редкие копирования всего массива.

Амортизированно — не значит «всегда быстро»

Оценка O(1)O(1) амортизированно говорит о суммарном времени, а не о задержке отдельного вызова. Из этого следуют практические ограничения:

  • Системы с жёсткими дедлайнами. Если от pop ждут ответа за микросекунды каждый раз — в обработке звука, играх, торговых системах, — редкий pop за O(n)O(n) даст выброс задержки. Там выбирают кольцевой буфер или связный список с честным O(1)O(1) в худшем случае.
  • Персистентные (неизменяемые) структуры. Амортизация опирается на то, что дорогая операция «тратит накопленное» один раз. Если старую версию очереди можно сохранить и вызывать pop на ней снова и снова, каждый раз будет переливаться весь inbox, и оценка развалится. В функциональных языках эту проблему решают ленивыми вычислениями (очереди Окасаки) или очередью Худа–Мелвилла, которая переливает понемногу на каждой операции и даёт O(1)O(1) в худшем случае.
  • Неосторожные «оптимизации». Если «для порядка» переливать outbox обратно в inbox перед каждым push, вы вернётесь к наивному O(n)O(n) на операцию. Свойство «каждый элемент переливается один раз» легко сломать.

Стек на очередях

Обратная задача (LeetCode 225): сделать стек (LIFO), пользуясь только операциями очереди — добавить в конец, забрать из начала, посмотреть начало, узнать размер. Здесь трюк с двумя контейнерами не помогает: очередь не разворачивает порядок, переливание из очереди в очередь сохраняет его как есть. Поэтому одна из операций будет стоить O(n)O(n).

Вариант 1: одна очередь, дорогой push

После добавления элемента прокручиваем очередь: перекладываем n−1n - 1 старых элементов из начала в конец. Новый элемент оказывается в голове, и pop/top работают за O(1)O(1).

from collections import deque class StackOneQueue: def __init__(self): self.q = deque() def push(self, x): self.q.append(x) # прокручиваем очередь, чтобы x оказался в голове for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self): return self.q.popleft() def top(self): return self.q[0] def empty(self): return not self.q s = StackOneQueue() for x in [1, 2, 3]: s.push(x) print(s.pop(), s.top(), s.pop(), s.pop(), s.empty()) # 3 2 2 1 True

deque здесь используется строго как очередь: append в конец и popleft из начала. Подробнее о самом деке — в статье про deque.

Вариант 2: две очереди, дорогой pop

Кладём как обычно, а при pop перекладываем все элементы, кроме последнего, во вспомогательную очередь, забираем последний и меняем очереди ролями.

from collections import deque class StackTwoQueues: def __init__(self): self.q = deque() self.buf = deque() def push(self, x): self.q.append(x) def pop(self): # оставляем в q только последний элемент, остальные — в buf while len(self.q) > 1: self.buf.append(self.q.popleft()) x = self.q.popleft() self.q, self.buf = self.buf, self.q return x def top(self): x = self.pop() self.push(x) return x def empty(self): return not self.q s = StackTwoQueues() for x in [1, 2, 3]: s.push(x) print(s.pop(), s.top(), s.pop(), s.pop(), s.empty()) # 3 2 2 1 True

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

Сравнение

Структураpushpoppeek/topПамять
Очередь на 2 стекахO(1)O(1)O(1)O(1) аморт.O(1)O(1) аморт.O(n)O(n)
Наивная очередьO(1)O(1)O(n)O(n)O(n)O(n)O(n)O(n)
Стек на 1 очередиO(n)O(n)O(1)O(1)O(1)O(1)O(n)O(n)
Стек на 2 очередяхO(1)O(1)O(n)O(n)O(n)O(n)O(n)O(n)

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

Сама по себе «очередь из двух стеков» нужна редко, но приём встречается в нескольких полезных местах.

  • Очередь с минимумом или максимумом. Стек легко научить отдавать минимум за O(1)O(1) — достаточно хранить рядом с каждым элементом минимум на его глубине. Соберите очередь из двух таких стеков, и получится очередь с минимумом: ответ — меньший из минимумов inbox и outbox. Это даёт минимум в скользящем окне за амортизированное O(1)O(1). Подробный код — в статье про Min Stack, альтернатива на деке — монотонная очередь.
  • Очереди в функциональных языках. Неизменяемый односвязный список — это по сути стек. Стандартная функциональная очередь строится из двух списков ровно по этой схеме.
  • Агрегаты по окну в потоковой обработке. Тот же приём с двумя стеками позволяет считать в скользящем окне любую ассоциативную операцию (сумму по модулю, НОД, произведение матриц), даже если у неё нет обратной и «вычесть» уходящий элемент нельзя.

Типичные ошибки

  • Переливать, когда outbox не пуст. Новые элементы ложатся поверх старых, и порядок FIFO ломается. Тест push 1, push 2, pop, push 3, pop сразу это покажет: должно вернуться 2.
  • Переливать обратно. Работает правильно, но за O(n)O(n) на операцию, и интервьюер спросит, зачем.
  • Забыть про peek. peek тоже должен переливать, если outbox пуст. Удобно вынести переливание в отдельный метод, как _shift выше, и звать его из обоих.
  • Проверять пустоту только по одному стеку. Очередь пуста, когда пусты оба стека.
  • Называть сложность просто O(1)O(1). Правильно — «O(1)O(1) амортизированно, O(n)O(n) в худшем случае для одной операции». Разница и есть суть задачи.
  • Использовать в Python list.pop(0) вместо очереди. Это O(n)O(n) на операцию, а в задаче про стек на очередях — ещё и нарушение условия. Очередь — это collections.deque с append/popleft.

Как это спрашивают на собеседовании

Обычно задача идёт как разминка на 10–15 минут, и вся ценность — в разговоре после кода:

  1. Напишите очередь на двух стеках. Хорошо сразу сказать про ленивое переливание, а не начинать с наивного варианта.
  2. Какая сложность pop? Ожидается ответ про амортизацию и объяснение через «каждый элемент перекладывается один раз» — это агрегатный метод, и обычно его достаточно.
  3. Follow-up: бывает ли у отдельной операции O(n)O(n)? Когда это проблема? Здесь пригодится пункт про задержки и персистентность.
  4. Обратная задача: стек на очереди. Почему здесь тот же трюк не работает?
  5. Иногда — очередь с максимумом и задача о максимуме в скользящем окне.

Если хотите закрепить работу со стеками на практике, решите задачи из блока ниже: валидные скобки и вычисление обратной польской записи — классика, где стек естественен. Про то, как вообще читать асимптотические оценки, — в статье про нотацию O большое.

Итог

  • Очередь на двух стеках: push в inbox, pop из outbox, переливание — только когда outbox пуст.
  • Каждый элемент перекладывается ровно один раз, поэтому mm операций стоят O(m)O(m): амортизированно O(1)O(1), хотя отдельный pop может стоить O(n)O(n).
  • Доказать оценку можно агрегатно (путь элемента), бухгалтерски (монетки на элементах) или через потенциал Φ=2⋅∣inbox∣\Phi = 2 \cdot |\text{inbox}|.
  • Амортизация не подходит для систем с жёсткими требованиями к задержке и ломается на персистентных версиях структуры.
  • Стек на очередях так не ускоряется: очередь не разворачивает порядок, поэтому push или pop всегда будет O(n)O(n).

Потренироваться в спокойной обстановке

Все задачи