Стек (LIFO)

Стек (LIFO): как это работает?

У стека два действия: положить и снять. Последнее положенное возвращается первым.

Массива для него вполне достаточно. Вставка пишет в конец, снятие читает и укорачивает.

Кладите всё, что открывается. Это может быть скобка, каталог или отложенное вычисление.

Снимайте всё, что закрывается. Потом проверьте, что снятое соответствует закрывающему элементу.

Пустой стек при снятии значит, что вход испорчен. Непустой стек в конце значит, что что-то не закрыли.

Ничего ниже вершины никогда не читается. Именно это ограничение и держит O(1) на операцию.

1. стек = []Проверяем строку ([]). Пока ничего не открыто.
2. стек = ['(']Открывающая круглая скобка положена в стек.
3. стек = ['(', '[']Квадратная скобка ложится сверху.
4. стек = ['(']Закрывающая квадратная снимает свою пару.
5. стек = []Закрывающая круглая снимает последнюю. Пустой стек значит верно.

function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}

Стек (LIFO): разбор примера

Упростить путь к файлу

Дан абсолютный путь, в котором бывают точки и двойные точки. Верните кратчайший путь с тем же смыслом.

Двойная точка поднимает на каталог вверх, одиночная ничего не меняет.

Разбейте путь по слешам и идите по частям подряд.

Кладите настоящее имя, снимайте на двойной точке, пропускайте пустые части и одиночные точки. В конце склейте стек.

function simplifyPath(path) {
    const stack = [];

    for (const part of path.split("/")) {
        if (part === "" || part === ".") continue;

        if (part === "..") {
            stack.pop(); // popping an empty stack is a no-op at the root
        } else {
            stack.push(part);
        }
    }

    return "/" + stack.join("/");
}

Стек (LIFO): когда применять?

Эти формулировки в условии ведут сюда:

• •корректные скобки / сбалансированные скобки
• •сопоставить самую недавнюю открывающую с ближайшей закрывающей
• •отмена, откат к последнему состоянию, вложенная структура
• •вычислить выражение с вложенными операторами
• •обработать в порядке, обратном порядку поступления

Стек (LIFO): с чем путают?

• Монотонный стек (Monotonic stack): Там стек упорядочен, и каждое снятие отвечает на вопрос. Обычный стек помнит лишь то, что открыто.
• Рекурсия (Recursion): Каждый рекурсивный вызов и так лежит на стеке. Свой стек снимает ограничение по глубине.
• Обход графа BFS / DFS (Graph BFS / DFS): Очередь даёт обход в ширину, стек даёт обход в глубину. Тот же обход, другой контейнер.
• Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min)): Дек читается и подрезается с обоих концов. Стек трогает только вершину.

Стек (LIFO): частые ошибки

• Снимают, не проверив на пустоту

  Снятие с пустого стека молча возвращает undefined. Проверьте размер, прежде чем верить значению.

• Не смотрят, что осталось в конце

  Непустой стек означает, что что-то не закрыли. Проверьте его после цикла.

• Берут shift вместо pop

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

• Кладут значения, когда нужны позиции

  Многие такие задачи спрашивают, как далеко назад что-то было. Кладите индекс и читайте значение по нему.

Стек (LIFO): задачи с собеседований

• Правильные скобки: Кладите открывающую, снимайте и сверяйте на закрывающей.
• Минимальный стек: Второй стек текущих минимумов отвечает за O(1).
• Обратная польская запись: Кладите числа, снимайте два на каждой операции.
• Упрощение пути: Кладите каталог, снимайте на двойной точке.
• Простой калькулятор: Кладите текущий результат перед открывающей скобкой.
• Декодирование строки: Кладите число повторов и текст перед каждой скобкой.
• Сравнение строк с забоем: Каждый забой снимает последний сохранённый символ.

Стек (LIFO): сложность по времени и памяти

O(n)

Каждая вставка и снятие стоят O(1), значит n операций дают O(n). Память в худшем случае O(n).