Стеки, очереди и амортизированный анализ

В редакторе выполнены действия «написать 4», «написать 7», затем отмена: должно исчезнуть 7. После нового действия 2 история содержит [4,2]. Команды push(4), push(7), pop(), push(2) делают именно это: последнее действие отменяется первым.

После оценки числа действий из лекции 01 перейдём к хранению данных. Во многих задачах важно, в каком порядке брать элементы. Начнём с самого простого правила — извлекать последний добавленный элемент.

Стек (Stack) — Контейнер с операциями push(x) и pop(): удаляется последний добавленный элемент (LIFO).

Стек удобно хранить как заполненный префикс массива. push записывает элемент в конец и увеличивает размер; pop уменьшает размер и возвращает последний элемент. При достаточной ёмкости обе операции занимают O(1).

push(x):
    A[n] = x
    n = n + 1

pop():
    assert n > 0
    n = n - 1
    return A[n]

Для [4, 7, 2] вершина равна 2: pop возвращает 2, затем 7. Инвариант массива прост: A[0..n) хранит живые элементы, а A[n] — следующее свободное место. top только читает A[n−1], не уменьшая n. На пустом стеке top и pop требуют отдельного соглашения об ошибке.

Стек выбирает конец, с которого доступны данные. Сменим это правило на порядок поступления и посмотрим, почему обычного массива со сдвигами недостаточно.

Добавим 4, затем 7, затем 2. Стек извлечёт 2, очередь — 4. Здесь одинаковые данные и команды, а разница только в правиле выбора следующего. Сравните также минимум из лекции 02, если уже знакомы с кучей.

У стека открыт один конец. Что изменится, если обслуживать элементы в порядке поступления? Например, запросы к серверу должны уходить в обработку от старых к новым: здесь нужен FIFO, а не LIFO.

Очередь (Queue) — Контейнер с enqueue(x) и dequeue(): удаляется самый давно добавленный элемент (FIFO).

Простая реализация удаляет A[0] и сдвигает остаток: для [4,7,2] приходится переместить 7 и 2. Если удалять так много раз из длинной очереди, набирается квадратичная работа. Оставим значения на месте и будем двигать только индекс head; освобождённые ячейки научимся использовать повторно.

Можно хранить элементы массива между указателями head и tail. Если оба указателя только увеличиваются, даже небольшая очередь со временем доберётся до края памяти.

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

Одних head и tail недостаточно, чтобы различить пустой и полный буфер: после полного оборота они могут совпасть. В этой лекции храним count отдельно. Запись идёт в (head + count) mod capacity, чтение — из head. При count = capacity сначала расширяем буфер или отклоняем добавление: молча затирать живой элемент нельзя.

Кольцевая индексация убрала сдвиги. Теперь отделим механизм хранения от задачи: используем стек для проверки вложенности.

Порядок извлечения становится полезным, когда сама задача вложенная. Рассмотрим строку ([{}]): последней открылась фигурная скобка, поэтому именно она должна закрыться первой. Стек хранит ещё не завершённые обязательства.

Пройдём ([{}]) посимвольно: сначала открытия (, [, {. Затем } ожидает { и снимает её; ] снимает [; ) снимает (. Для ([)] после ( и [ символ ) ожидает (, но вершина [. Поэтому ответ отрицательный, хотя открытий и закрытий поровну.

Во время вызова функции сохраняются адрес возврата и данные текущего вызова: поэтому цепочка рекурсивных вызовов естественно имеет дисциплину LIFO.

Другое применение — разбор вложенных конструкций, например нескольких видов скобок. Каждая закрывающая скобка должна соответствовать последней ещё открытой скобке.

stack = []
for c in expression:
    if c is opening:
        stack.push(c)
    else if c is closing:
        if stack.empty() or not matches(stack.top(), c):
            return false
        stack.pop()
return stack.empty()

В строке ([)] ошибка обнаруживается на первом ). Сначала самостоятельно реализуйте проверку скобок и отмену команд. Затем переходите к монотонному стеку: его дополнительное правило удаляет слишком большие вершины; пример трассировки находится в практике.

def valid_brackets(text: str) -> bool:
    stack = []
    opening = {')': '(', ']': '[', '}': '{'}
    for c in text:
        if c in '([{':
            stack.append(c)
        elif c in opening:
            if not stack or stack.pop() != opening[c]:
                return False
        else:
            return False
    return not stack

print(str(valid_brackets('([{}])')).lower(), str(valid_brackets('([)]')).lower())

fn valid_brackets(text: &str) -> bool {
    let mut stack = Vec::new();
    for c in text.bytes() {
        let expected = match c {
            b'(' | b'[' | b'{' => { stack.push(c); continue; }
            b')' => b'(', b']' => b'[', b'}' => b'{', _ => return false,
        };
        if stack.pop() != Some(expected) { return false; }
    }
    stack.is_empty()
}
fn main() { println!("{} {}", valid_brackets("([{}])"), valid_brackets("([)]")); }

true false

Мы уже получили линейную обработку строки. Осталось проверить скрытое предположение о свободной памяти под растущий стек.

def valid_brackets(text):
	# Напишите решение
	pass

Что произойдёт, когда все 4 ячейки уже заняты, а приходит пятый элемент? size=4 означает число живых элементов, capacity=4 — число выделенных мест. Можно выделить 5 ячеек или 8; в обоих случаях сейчас копируются четыре старых значения, но следующая вставка будет стоить по-разному.

До сих пор ёмкость массива считалась достаточной. В реальной задаче число будущих элементов часто неизвестно. Нельзя молча сохранить оценку O(1): сначала посчитаем цену выделения новой памяти и переноса старых элементов.

Если увеличивать массив на одну ячейку при каждом переполнении, копирование 1 + 2 + … + (n−1) элементов приведёт к Θ(n²) суммарной работе для n вставок.

При увеличении ёмкости в фиксированное число раз больше единицы копирование происходит редко; общая стоимость n последовательных вставок O(n). Но отдельная вставка с перевыделением всё ещё стоит O(n).

После 9 добавлений ёмкости 1, 2, 4, 8, 16 дают 1 + 2 + 4 + 8 = 15 копирований и ещё 9 записей новых элементов. Большая цена последней вставки не превращает всю последовательность в квадратичную. Обратное сжатие при каждом pop может вызвать частое копирование; для уменьшения ёмкости нужны разнесённые пороги, например четверть заполнения.

def growth_cost(n: int) -> tuple[int, int]:
    size, capacity, copies = 0, 1, 0
    for _ in range(n):
        if size == capacity:
            copies += size
            capacity *= 2
        size += 1
    return copies, copies + n

print(*growth_cost(9))

fn growth_cost(n: usize) -> (usize, usize) {
    let (mut size, mut capacity, mut copies) = (0, 1, 0);
    for _ in 0..n {
        if size == capacity { copies += size; capacity *= 2; }
        size += 1;
    }
    (copies, copies + n)
}
fn main() { let (copies,total)=growth_cost(9); println!("{} {}",copies,total); }

15 24

Геометрическая сумма объяснила общий результат. Дадим этому виду оценки точное название и отличим его от среднего по случайным входам.

Посчитаем десять вставок, начиная с пустого массива ёмкости 1. Их цены: 1,2,3,1,5,1,1,1,9,1. Накопленная работа: 1,3,6,7,12,13,14,15,24,25. Девятая операция дорогая, однако все десять потребовали 25 действий. Таблица в модели расширяемого массива показывает тот же расчёт для любого выбранного числа вставок.

После удвоений отдельные вставки резко отличаются по времени. Чтобы описать такую структуру честно, сменим единицу анализа: вместо одного вызова рассмотрим всю последовательность, начиная с пустого состояния.

Амортизированный анализ (Amortized analysis) — Метод оценки суммарной стоимости последовательности операций с учётом редких дорогих действий.

Вместо требования «каждая операция быстрая» доказывают, что сумма затрат на любую последовательность из m операций ограничена O(m). Это не вероятностное среднее и не утверждение о конкретном замере процессора.

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

Для основного маршрута достаточно суммы копирований и подсчёта судьбы одного элемента. Три формальных метода — необязательное углубление; дальше можно перейти сразу к очереди на двух стеках.

Выполним push(3), push(8), pop(), push(5), pop(). Сначала input=[3,8], output пуст. Перенос разворачивает его в output=[8,3], pop выдаёт 3. Новая 5 идёт в input; следующий pop берёт оставшуюся 8 из output без переноса. Только когда output опустеет, можно переносить 5.

Теперь применим анализ к новой реализации FIFO. Входной стек принимает элементы, выходной отдаёт их в обратном порядке. Второе обращение порядка при переносе позволяет получить именно очередь.

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

enqueue(x):
    input.push(x)

dequeue():
    if output.empty():
        while not input.empty():
            output.push(input.pop())
    assert not output.empty()
    return output.pop()

Одиночное извлечение при полном переносе может быть O(n), но суммарно m операций — O(m). Следовательно, обе операции выполняются за O(1) амортизированно.

Для enqueue(3), enqueue(8), dequeue(), enqueue(5), dequeue() ответы равны 3 и 8. Важно переносить входной стек только при пустом выходном: иначе новые элементы окажутся перед старыми. За одну линейную историю каждый элемент проходит input и output не больше одного раза, поэтому m операций требуют O(m) работы и O(n) памяти.

class TwoStackQueue:
    def __init__(self):
        self.incoming = []
        self.outgoing = []

    def push(self, value):
        self.incoming.append(value)

    def pop(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())
        return self.outgoing.pop() if self.outgoing else None

q = TwoStackQueue()
q.push(3)
q.push(8)
first = q.pop()
q.push(5)
print(first, q.pop(), q.pop())

#[derive(Default)]
struct TwoStackQueue { incoming: Vec<i64>, outgoing: Vec<i64> }
impl TwoStackQueue {
    fn push(&mut self, value: i64) { self.incoming.push(value); }
    fn pop(&mut self) -> Option<i64> {
        if self.outgoing.is_empty() {
            while let Some(x) = self.incoming.pop() { self.outgoing.push(x); }
        }
        self.outgoing.pop()
    }
}
fn main() {
    let mut q = TwoStackQueue::default(); q.push(3); q.push(8);
    let first=q.pop().unwrap(); q.push(5);
    println!("{} {} {}",first,q.pop().unwrap(),q.pop().unwrap());
}

3 8 5

Каждый элемент проходит каждый стек не более одного раза за одну историю команд: так получается суммарное O(m). Практика ниже закрепляет очередь. Деамортизация следующей главы — дополнительный эксперимент.

def queue_results(commands):
	# Напишите решение
	pass

Справочник собирает определения из разобранных разделов. Используйте поиск, если нужно восстановить термин; затем переходите к оценке ограничений и задачам для самостоятельного решения.

Общий справочник всех лекций ↗

Найдено: 12 из 12

Сначала подставьте максимальные размеры из условия в оценку времени и памяти. Оценка числа действий — ориентир: константы, язык и ввод проверяются отдельно.

Сравнение уже разобранных структур

Считаем всю последовательность

Для q = 200 000 команд сумма 1 + … + q достигает примерно 2·10¹⁰. Сдвиг при каждом извлечении из начала массива опасен, даже если сама очередь часто короткая. Сначала выясните, может ли вход специально накопить длинный хвост.

Стек, кольцевая очередь и очередь на двух стеках дают O(q) суммарной работы в подходящей модели. Для динамического массива отдельно учитывайте копирования: удвоение укладывается в O(q), единичное расширение — нет.

Вложенный цикл не всегда квадрат

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

Память и худший отдельный шаг

Если глубина вложенности не ограничена отдельно, стек скобок может хранить n открытий. При n = 10⁶ это O(n) памяти; Python-объекты и целые индексы заметно тяжелее одного машинного байта. Для одних ASCII-скобок выбирайте компактное представление, если лимит мал.

Амортизированное время подходит для общего лимита контеста. Оно не доказывает ограничение задержки каждого запроса. В тестах проверьте пустую структуру, одно значение, совпадающие элементы, полный оборот буфера и длинную серию добавлений перед первым извлечением.

Разминка: скобки, отмена, очередь

Решите эти задачи без внешнего сайта. Используйте стек для отмены и два стека для очереди; затем переходите к Min Stack и монотонному стеку.

def valid_brackets(text):
	# Напишите решение
	pass

def undo_results(commands):
	# Напишите решение
	pass

def queue_results(commands):
	# Напишите решение
	pass

Основное применение: Valid Parentheses и Implement Queue using Stacks, затем Min Stack и Daily Temperatures. Largest Rectangle — необязательное испытание после трассировки монотонного стека.

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.