Очередь на двух стеках и стек на очередях: амортизированный анализ
Как сделать очередь из двух стеков за амортизированное O(1) и стек из очереди: код на Python и JavaScript, метод потенциалов и бухгалтерский метод, худший случай и типичные ошибки.
Коротко
| Вопрос | Ответ |
|---|---|
| Очередь на двух стеках | inbox для push, outbox для pop; переливаем, только когда outbox пуст |
| Сложность очереди | Амортизированно на операцию, но отдельный pop может стоить |
| Почему амортизированно | Каждый элемент перекладывается из стека в стек ровно один раз за всю жизнь |
| Стек на очереди | После push прокручиваем очередь, чтобы новый элемент оказался в голове: push за |
| Что проверяют на интервью | Умение объяснить амортизацию: агрегатно, «монетками» или через потенциал |
Задачи «очередь через стеки» (LeetCode 232) и «стек через очереди» (LeetCode 225) выглядят как разминка: никто в продакшене не собирает очередь из двух массивов. Но их любят на собеседованиях за follow-up: «а какая сложность у pop?». Правильный ответ — «амортизированно » — и дальше нужно уметь объяснить, что это значит и почему это не то же самое, что в худшем случае. Разберём обе задачи, три способа доказать оценку и места, где амортизация подводит.
Условие
Нужно реализовать очередь (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 стоит , а операций — . Лишняя работа очевидна: мы аккуратно разворачиваем элементы в правильный порядок, а потом зачем-то разворачиваем обратно.
Ключевая идея: не переливать обратно
Заведём два стека с разными ролями:
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
Разбор на примере
Проследим состояние стеков (вершина справа):
| Операция | inbox | outbox | Результат | Что произошло |
|---|---|---|---|---|
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 сделал три перекладывания, следующие два — ни одного. Дорогие операции бывают, но редко, и каждая «оплачивает» несколько последующих дешёвых.
Амортизированный анализ
Худший случай одной операции — : если положить миллион элементов и вызвать pop, он переложит миллион. Но такой pop не может повторяться подряд. Амортизированная стоимость — это средняя стоимость операции в худшей последовательности операций. Это не среднее по случайным входам: никакой вероятности здесь нет, оценка гарантирована для любой последовательности.
Докажем, что последовательность из операций над пустой очередью стоит . Есть три стандартных способа, и на собеседовании хватит любого — но полезно знать все.
Агрегатный метод: считаем путь каждого элемента
Проследим жизнь одного элемента. За всё время он:
- кладётся в
inbox— одна операция; - снимается с
inboxпри переливании — одна; - кладётся в
outbox— одна; - снимается с
outboxприpop— одна.
Ни один шаг не повторяется: элемент никогда не возвращается из outbox в inbox. Значит, на элемент приходится не больше четырёх операций со стеками, а на операций очереди — не больше . В среднем .
Проверим это экспериментально, посчитав элементарные операции со стеками:
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
вставок и извлечений — это операций очереди и ровно операций со стеками: по две на операцию очереди, как и предсказывает подсчёт.
Бухгалтерский метод: монетки на элементах
Будем брать за каждый push три монетки вместо одной. Одна тратится на сам push, две кладутся «на элемент» в inbox. Когда приходит время переливать, у каждого элемента в inbox уже лежат две монетки: одна оплачивает снятие с inbox, вторая — укладку в outbox. Сам pop стоит одну монетку.
Баланс никогда не уходит в минус, поэтому реальная стоимость любой последовательности не больше суммы выставленных счетов: за push и за pop. Обе — константы.
Метод потенциалов
Формальная версия той же идеи. Введём потенциал — функцию состояния структуры, которая неотрицательна и в начале равна нулю:
Амортизированная стоимость операции — реальная стоимость плюс изменение потенциала: . Посчитаем:
push: , потенциал растёт на , итого ;popбез переливания: , , итого ;popс переливанием элементов: , потенциал падает на , итого .
Сумма амортизированных стоимостей равна сумме реальных плюс . Значит, реальная стоимость не больше — то же .
Потенциал — это «накопленная работа, которую ещё предстоит сделать»: элементы в inbox рано или поздно придётся переложить. Тот же приём объясняет, почему динамический массив добавляет элемент за амортизированное , несмотря на редкие копирования всего массива.
Амортизированно — не значит «всегда быстро»
Оценка амортизированно говорит о суммарном времени, а не о задержке отдельного вызова. Из этого следуют практические ограничения:
- Системы с жёсткими дедлайнами. Если от
popждут ответа за микросекунды каждый раз — в обработке звука, играх, торговых системах, — редкийpopза даст выброс задержки. Там выбирают кольцевой буфер или связный список с честным в худшем случае. - Персистентные (неизменяемые) структуры. Амортизация опирается на то, что дорогая операция «тратит накопленное» один раз. Если старую версию очереди можно сохранить и вызывать
popна ней снова и снова, каждый раз будет переливаться весьinbox, и оценка развалится. В функциональных языках эту проблему решают ленивыми вычислениями (очереди Окасаки) или очередью Худа–Мелвилла, которая переливает понемногу на каждой операции и даёт в худшем случае. - Неосторожные «оптимизации». Если «для порядка» переливать
outboxобратно вinboxперед каждымpush, вы вернётесь к наивному на операцию. Свойство «каждый элемент переливается один раз» легко сломать.
Стек на очередях
Обратная задача (LeetCode 225): сделать стек (LIFO), пользуясь только операциями очереди — добавить в конец, забрать из начала, посмотреть начало, узнать размер. Здесь трюк с двумя контейнерами не помогает: очередь не разворачивает порядок, переливание из очереди в очередь сохраняет его как есть. Поэтому одна из операций будет стоить .
Вариант 1: одна очередь, дорогой push
После добавления элемента прокручиваем очередь: перекладываем старых элементов из начала в конец. Новый элемент оказывается в голове, и pop/top работают за .
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 честно стоит , потому что элементы прокручиваются снова и снова, а не один раз за жизнь. В этом принципиальная асимметрия двух задач.
Сравнение
| Структура | push | pop | peek/top | Память |
|---|---|---|---|---|
| Очередь на 2 стеках | аморт. | аморт. | ||
| Наивная очередь | ||||
| Стек на 1 очереди | ||||
| Стек на 2 очередях |
Где идея пригождается на практике
Сама по себе «очередь из двух стеков» нужна редко, но приём встречается в нескольких полезных местах.
- Очередь с минимумом или максимумом. Стек легко научить отдавать минимум за — достаточно хранить рядом с каждым элементом минимум на его глубине. Соберите очередь из двух таких стеков, и получится очередь с минимумом: ответ — меньший из минимумов
inboxиoutbox. Это даёт минимум в скользящем окне за амортизированное . Подробный код — в статье про Min Stack, альтернатива на деке — монотонная очередь. - Очереди в функциональных языках. Неизменяемый односвязный список — это по сути стек. Стандартная функциональная очередь строится из двух списков ровно по этой схеме.
- Агрегаты по окну в потоковой обработке. Тот же приём с двумя стеками позволяет считать в скользящем окне любую ассоциативную операцию (сумму по модулю, НОД, произведение матриц), даже если у неё нет обратной и «вычесть» уходящий элемент нельзя.
Типичные ошибки
- Переливать, когда
outboxне пуст. Новые элементы ложатся поверх старых, и порядок FIFO ломается. Тестpush 1, push 2, pop, push 3, popсразу это покажет: должно вернуться2. - Переливать обратно. Работает правильно, но за на операцию, и интервьюер спросит, зачем.
- Забыть про
peek.peekтоже должен переливать, еслиoutboxпуст. Удобно вынести переливание в отдельный метод, как_shiftвыше, и звать его из обоих. - Проверять пустоту только по одному стеку. Очередь пуста, когда пусты оба стека.
- Называть сложность просто . Правильно — « амортизированно, в худшем случае для одной операции». Разница и есть суть задачи.
- Использовать в Python
list.pop(0)вместо очереди. Это на операцию, а в задаче про стек на очередях — ещё и нарушение условия. Очередь — этоcollections.dequeсappend/popleft.
Как это спрашивают на собеседовании
Обычно задача идёт как разминка на 10–15 минут, и вся ценность — в разговоре после кода:
- Напишите очередь на двух стеках. Хорошо сразу сказать про ленивое переливание, а не начинать с наивного варианта.
- Какая сложность
pop? Ожидается ответ про амортизацию и объяснение через «каждый элемент перекладывается один раз» — это агрегатный метод, и обычно его достаточно. - Follow-up: бывает ли у отдельной операции ? Когда это проблема? Здесь пригодится пункт про задержки и персистентность.
- Обратная задача: стек на очереди. Почему здесь тот же трюк не работает?
- Иногда — очередь с максимумом и задача о максимуме в скользящем окне.
Если хотите закрепить работу со стеками на практике, решите задачи из блока ниже: валидные скобки и вычисление обратной польской записи — классика, где стек естественен. Про то, как вообще читать асимптотические оценки, — в статье про нотацию O большое.
Итог
- Очередь на двух стеках:
pushвinbox,popизoutbox, переливание — только когдаoutboxпуст. - Каждый элемент перекладывается ровно один раз, поэтому операций стоят : амортизированно , хотя отдельный
popможет стоить . - Доказать оценку можно агрегатно (путь элемента), бухгалтерски (монетки на элементах) или через потенциал .
- Амортизация не подходит для систем с жёсткими требованиями к задержке и ломается на персистентных версиях структуры.
- Стек на очередях так не ускоряется: очередь не разворачивает порядок, поэтому
pushилиpopвсегда будет .