Стек
LIFO: последний вошёл — первым вышел. push и pop за O(1) с одной стороны.
1function isBalanced(s: string): boolean {2 const stack: string[] = []3 4 for (const ch of s) {5 if (ch === '(') {6 stack.push(ch)7 } else {8 if (stack.length === 0) return false9 stack.pop()10 }11 }12 13 return stack.length === 014}Проблема
Отслеживать вложенность: скобки, вызовы функций, пути назад. Нужно помнить «последнее незакрытое» и возвращаться к нему — стек делает это естественной дисциплиной доступа.
Что вы видите
Входная строка скобок; стек растёт на «(» и схлопывается на «)». Если «)» приходит в пустой стек — сразу дисбаланс; если в конце стек не пуст — есть незакрытые.
Как это работает
Стек — массив с операциями только с вершины: push/pop/peek, все O(1). На нём держатся: рекурсия (стек вызовов), undo, back-button, обходы в глубину. Ограничение — доступ только к вершине.
Пошаговый разбор
- 01
push
Элемент кладётся на вершину.
- 02
pop
Вершина снимается — последним вошёл, первым ушёл.
- 03
peek
Посмотреть вершину не снимая.
- 04
Инвариант скобок
Каждое «)» закрывает последнюю «(».
Complexity и ограничения
O(1) на операцию, память O(n).
Edge cases
- Закрывающая в пустом стеке
Дисбаланс обнаружен мгновенно.
- Незакрытые в конце
Стек не пуст — тоже дисбаланс.
- Переполнение
Стек вызовов ограничен — глубокая рекурсия падает.
Где встречается в реальности
Стек вызовов
Рекурсия — это стек: переполнение = stack overflow.
Undo/Redo
История правок в редакторах.
Back-навигация
Кнопка «назад» ходит по стеку страниц.
Связанные алгоритмы
«Как одна структура закрывает скобки, undo и рекурсию»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.