Очередь на двух стеках и дека

Если ты умеешь доказать амортизированное O(1) для очереди на двух стеках (каждый элемент переливается один раз) и знаешь, что такое дека, листай до «Теперь сам».

Как думаешь, можно ли собрать очередь из стеков

Стек и очередь - противоположности: один отдаёт в обратном порядке, другой в прямом. Казалось бы, из стека очередь не сделать. Но переворот легко чинится ВТОРЫМ переворотом: перевернул дважды - вернул прямой порядок. Стек переворачивает порядок; перелей стек в другой стек - и порядок перевернётся снова, то есть станет прямым. На этом и стоит очередь из двух стеков. И заметь: у нас в кармане уже есть отличный стек - list с append/pop, обе O(1). Значит, очередь можно собрать из того, что массив делает дёшево, не трогая дорогую голову вовсе.

На что это похоже

Два лотка для бумаг: «входящие» и «на выход». Новые документы бросаешь во «входящие» - они копятся стопкой, свежий сверху. Когда надо взять самый СТАРЫЙ (по правилам очереди), а лоток «на выход» пуст, ты перекладываешь всю стопку из «входящих» в «на выход» - и она переворачивается: самый старый оказывается сверху. Дальше берёшь с «на выход», пока он не опустеет, и только тогда переливаешь снова. Каждый документ переложат из лотка в лоток ровно один раз - не на каждый запрос, а один раз за свою жизнь.

Механизм: два стека и перелив

Держим два стека: in (сюда enqueue) и out (отсюда dequeue).

• enqueue(x): push(x) в in. Всегда O(1).
• dequeue(): если out НЕ пуст - pop с out, O(1). Если out пуст - сначала переливаем: пока in не опустеет, pop из in и push в out (перелив переворачивает порядок, и старейший оказывается на вершине out), потом pop с out.

Перелив стоит O(k), где k - сколько было в in. Кажется дорого. Но посмотри на жизнь ОДНОГО элемента: его push-нули в in (1 шаг), при переливе pop-нули из in (1) и push-нули в out (1), при выдаче pop-нули из out (1). Четыре дешёвых шага за всю жизнь, и переливается он РОВНО раз - из in в out он попадает единожды и обратно не возвращается. Значит n элементов дают не больше 4n шагов на всю серию, то есть O(1) амортизированно на операцию.

Правило

Очередь на двух стеках: in для прихода, out для ухода. enqueue - push в in (O(1)). dequeue - pop с out, а если out пуст, сперва перелить в него весь in (перелив переворачивает порядок), потом снять. Отдельный перелив O(k), но каждый элемент переливается ровно раз за жизнь, поэтому dequeue - O(1) АМОРТИЗИРОВАННО. Это та же амортизация, что у динамического массива: редкая дорогая операция, оплаченная дешёвыми.

Разбор: докажем O(1) методом потенциалов

Возьмём потенциал Φ = 2 · (размер стека in) - по ДВА за каждый элемент в in. Почему по два: каждый элемент, лежащий в in, ждёт двух будущих дешёвых операций - pop из in и push в out при переливе, - и заранее носит на них запас 2. Φ неотрицателен и в пустой очереди равен нулю: условия метода из прошлого раздела выполнены. Считаем ĉ = c + ΔΦ.

• enqueue: настоящая цена c = 1 (один push в in), in вырос на один, значит Φ вырос на 2. Амортизированно ĉ = 1 + 2 = 3 = O(1).
• dequeue без перелива (out не пуст): c = 1 (pop с out), Φ не изменился (in не трогали). ĉ = 1 + 0 = 1 = O(1).
• dequeue с переливом (in содержал k): перелив - это k снятий из in и k добавлений в out, то есть 2k дешёвых операций, плюс само снятие с out (1): c = 2k + 1. При этом Φ упал с 2k до 0, то есть ΔΦ = −2k. Амортизированно ĉ = (2k + 1) − 2k = 1 = O(1).

Во всех трёх случаях ĉ - константа. Дорогой перелив (его 2k) гасится падением потенциала, который до этого накопили дешёвые enqueue (каждый поднял Φ на 2 - как раз на будущие pop из in и push в out). Ровно как копирование при удвоении массива, и коэффициент 2 тот же, что в Φ = 2·num − size.

Разбор: кольцевой буфер или два стека - что когда

Оба дают быструю очередь без сдвига головы, но по-разному. Кольцевой буфер - O(1) в ХУДШЕМ случае на каждую операцию (никаких переливов, всегда одна запись и сдвиг индекса), но ёмкость фиксирована и рост требует ручного удвоения. Очередь на двух стеках - O(1) лишь АМОРТИЗИРОВАННО (отдельный dequeue с переливом бывает O(k)), зато сама собой растёт (стеки на динамических массивах) и не знает переполнения. Выбор - по знакомому правилу: нужен предсказуемый худший случай на каждый вызов (реальное время) - кольцевой буфер; хватает гарантии по серии и хочется, чтобы очередь росла сама - два стека. Разные виды цены под разные задачи, ровно как в главе про инвариант.

Что ломается без этого

Первая ошибка - переливать in в out, когда в out ещё что-то лежит. Новые элементы лягут поверх старых и выйдут раньше них: enqueue 1, enqueue 2, dequeue, enqueue 3, dequeue выдаст 1 и 3 вместо 1 и 2. Наивная починка - после каждого dequeue переливать out обратно в in - порядок возвращает, но тогда каждый элемент льётся многократно, и O(1) амортизированно рассыпается в O(n). Условие «переливаем лишь при пустом out» держит и порядок, и цену: только оно гарантирует «ровно один перелив за жизнь». Вторая - принять амортизированную O(1) за гарантию на каждый вызов: отдельный dequeue с переливом честно стоит O(k), и там, где важен худший ОДИН шаг, нужен кольцевой буфер. Третья - перепутать концы и снимать/класть не туда, сломав порядок FIFO.

Зачем это в работе

Это классическая задача (в CLRS - упражнение к главе про амортизацию), и её любят на собеседованиях: «реализуйте очередь на двух стеках» проверяет, понимаешь ли ты амортизацию, а не только определения. На практике же за словом «очередь» в стандартных библиотеках стоит обычно дека - collections.deque в Python, ArrayDeque в Java, - структура с дешёвыми операциями на ОБОИХ концах: O(1) добавить и снять и слева, и справа. Дека обобщает и стек (работай одним концом), и очередь (клади с одного, снимай с другого), поэтому одной струк­турой закрывают оба случая. Внутри дека - либо кольцевой буфер, либо двусвязный список: обе реализации ты теперь знаешь и понимаешь, откуда у них O(1).

Теперь сам

В очередь на двух стеках сделали enqueue(1), enqueue(2), enqueue(3), потом три dequeue(). Опиши, что происходит со стеками in и out, в каком порядке выйдут числа и сколько всего переливов случится. Почему это O(1) амортизированно, а не O(n²)?