Стеки

Чтобы проверить, что скобки в {[()()]} правильно образуют пары, нужен один стек и 8 добавлений и извлечений, по одному на каждую скобку.

Последним пришёл, первым ушёл

Представь стопку тарелок. Чистую тарелку кладёшь наверх, а когда нужна тарелка, берёшь сверху. Тарелка, положенная последней, уходит первой. Стек является структурой данных ровно с этим правилом, оно называется «последним пришёл, первым ушёл» (LIFO). У него две главные операции: push кладёт значение наверх, а pop снимает верхнее значение и возвращает его. Многие стеки предлагают и peek, которая смотрит на верх, ничего не снимая.

В конспектах MIT 6.006 стек является частным случаем интерфейса последовательности: insert last(x) и delete last(). Это уже подсказывает, как его построить. Положи значения в динамический массив и считай конец массива верхом. В прошлом уроке конец был дешёвой стороной, поэтому push и pop стоят по 1 шагу (амортизированно, из-за редких копирований). Размер стека ничего не меняет. Снять значение со стека из 3 значений или из 3 миллионов значит сделать один и тот же шаг.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, добавлено последним
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Проверка скобок

Классическое применение стека: проверка, сбалансированы ли скобки, это делает каждый редактор кода и компилятор. Читай текст слева направо. Каждая открывающая скобка, (, [ или {, кладётся в стек. Каждая закрывающая скобка должна совпадать с открывающей на верху стека: если совпадает, сними эту открывающую; если стек пуст или наверху скобка другого вида, строка не сбалансирована. В конце стек должен быть пуст, иначе какая-то открывающая скобка так и не закрылась.

Попробуй строки в лаборатории. {[()()]} требует 4 добавления и 4 извлечения, 8 шагов, и заканчивается пустым стеком. ([)] ломается на третьем символе: ) приходит, когда наверху [. (() дочитывается до конца, и одна ( остаётся лишней. Почему для этой работы подходит стек? Скобки вкладываются друг в друга, и последняя открытая должна закрыться первой. Это и есть «последним пришёл, первым ушёл».

Где ещё встречаются стеки

• Стек вызовов. Когда функция a вызывает b, а b вызывает c, компьютер кладёт запись для каждого вызова. Когда c возвращает результат, её запись снимается, и b продолжает с того места, где остановилась. Бесконечная рекурсия переполняет этот стек, отсюда ошибка «переполнение стека» (stack overflow).
• Отмена. Редактор кладёт в стек каждое изменение. Отмена снимает последнее изменение и откатывает его.
• Кнопка «Назад». Браузер кладёт в стек каждую страницу, с которой ты уходишь; «Назад» снимает последнюю.
• Поиск в глубину. В курсе об алгоритмах стек помогал зайти в лабиринте как можно глубже, прежде чем возвращаться.