Очередь на двух стеках и амортизация

Стек умеет добавлять и удалять с одного конца. Очередь — добавлять с одного, удалять с другого. Задача: собрать очередь из двух стеков.

Задача звучит как упражнение, и во многих контестах она им и является — стандартными контейнерами пользоваться запрещают. Но настоящая её ценность в другом: на ней впервые видно, что значит «в среднем за константу».

Наивная реализация

Простейший способ сделать очередь из вектора — не удалять из начала вообще, а держать указатель:

vector<int> data;
int head = 0;

void push(int value) { data.push_back(value); }
int  front()         { return data[head]; }
void pop()           { head++; }

Все операции — честная константа. Проблема одна: память не освобождается. Все элементы, когда-либо попавшие в очередь, остаются в векторе навсегда.

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

Два стека

Второй способ тратит ровно столько памяти, сколько элементов лежит сейчас.

Идея: два стека, повёрнутые друг к другу. Один принимает новые элементы (tail), другой отдаёт старые (head). Когда отдающий пуст — переливаем в него всё из принимающего, и порядок при этом сам собой переворачивается.

flowchart LR
    IN["push"] --> T["tail<br/>(принимает)"]
    T -.->|"когда head пуст:<br/>переливаем всё"| H["head<br/>(отдаёт)"]
    H --> OUT["pop / front"]

vector<int> head, tail;

void push(int value) { tail.push_back(value); }

void moveIfNeeded() {
    if (head.empty())
        while (!tail.empty()) {
            head.push_back(tail.back());
            tail.pop_back();
        }
}

int  front() { moveIfNeeded(); return head.back(); }
void pop()   { moveIfNeeded(); head.pop_back(); }

Проверено против deque: на двадцати тысячах случайных сценариев из сорока операций каждый результат совпал.

Обратите внимание, что переливание происходит только когда head пуст. Переливать при каждом обращении нельзя — тогда порядок собьётся, а работа станет квадратичной.

Почему это быстро

Одна операция pop может стоить $O(n)$ — если переливать приходится сразу тысячу элементов. Казалось бы, катастрофа.

Но посмотрим на суммарную работу. Каждый элемент за всю свою жизнь участвует ровно в трёх операциях: его один раз положили в tail, один раз перелили в head, один раз сняли. Больше с ним ничего не происходит — обратно в tail он не попадает.

Значит, на $n$ операций приходится не более $3n$ элементарных действий, то есть в среднем три действия на операцию.

Это называется амортизированной сложностью: отдельная операция может быть дорогой, но последовательность из $n$ операций стоит $O(n)$. И для программы важно именно второе.

Где ещё встречается амортизация

Тот же тип рассуждения объясняет три вещи, которые вы уже используете:

push_back вектора. При нехватке места вектор переезжает в новую область памяти вдвое большего размера — это стоит линию. Но следующий переезд случится не раньше, чем размер снова удвоится. Суммарно на $n$ добавлений приходится $n + n/2 + n/4 + \dots < 2n$ копирований, то есть константа на добавление.

Стек ближайших меньших. Внутренний while может снять со стека сразу половину элементов, но каждый элемент кладётся и снимается один раз — снова линия суммарно.

Два указателя. Внутренний цикл иногда пробегает много шагов, но правый указатель никогда не идёт назад.

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

Это же и главный признак того, что «два вложенных цикла» не означают квадрат. Если внутренний цикл продвигает указатель, который никогда не откатывается, — сложность линейная, сколько бы циклов ни было написано.

Что брать на практике

нужно	берите
добавить и снять с конца	vector
очередь, каждый элемент один раз	vector + указатель головы
очередь общего вида	queue (внутри deque)
оба конца и доступ по индексу	deque
задача требует реализовать вручную	два стека

deque универсален, но платит за это: он хранит данные блоками, а не одним куском, поэтому обход по нему медленнее, чем по вектору, а обращение по индексу требует двух разыменований вместо одного. Когда данных много и нужен только конец — вектор быстрее.

И обратное: queue, реализованная поверх deque, для алгоритмов вроде обхода в ширину подходит идеально, и переписывать её на два стека незачем.