Реализация очереди через два стека: почему амортизированно O(1) на операцию?
Знаю, что очередь можно сделать на двух стеках. Реализация понятна, но не пойму, почему говорят, что push и pop амортизированно O(1), если иногда при pop нужно перелить весь один стек в другой за O(n).
2 ответа
Держим два стека: in (для добавления) и out (для извлечения). push всегда кладёт в in. pop/front берёт из out; если out пуст — переливаем весь in в out (порядок при этом разворачивается, как и нужно для FIFO).
std::stack<int> in, out;
void push(int x) { in.push(x); }
void moveIfNeeded() {
if (out.empty())
while (!in.empty()) { out.push(in.top()); in.pop(); }
}
int front() { moveIfNeeded(); return out.top(); }
void pop() { moveIfNeeded(); out.pop(); }
Почему амортизированно O(1): да, отдельный pop может стоить O(n) на переливание. Но каждый элемент за всю свою жизнь: один раз кладётся в in, один раз перекладывается из in в out, один раз снимается с out. Итого ровно 3 операции на элемент за весь срок жизни, независимо от того, когда случаются переливания. На последовательности из n операций суммарная работа O(n) → амортизированно O(1) на операцию.
Формально (метод потенциалов): потенциал Φ = размер in. Каждый push добавляет +1 к потенциалу (амортизированная цена 2). Переливание k элементов стоит k реальной работы, но уменьшает потенциал на k, так что амортизированная цена pop = O(1). Это тот же приём, что и с удвоением массива: «дорогая операция оплачивается заранее накопленным потенциалом».
Полезное следствие: эта конструкция — основа «очереди с минимумом» за амортизированное O(1). Делаешь не просто стеки, а стеки-с-минимумом (каждый элемент хранит ещё и минимум по стеку под собой). Минимум очереди = min(минимум in, минимум out). Это позволяет, например, считать минимум на скользящем окне переменной длины, когда монотонный дек неудобен. Грабля: если требуется строго O(1) в худшем случае (а не амортизированно) — нужна более сложная «real-time queue» с поэтапным переливанием; но для олимпиад почти всегда хватает амортизированной версии.