Стек на массиве

Представьте стопку тарелок на кухне. Чистую тарелку кладут сверху, и берут тоже сверху. Тарелка, которую положили последней, первой и уйдёт, а нижняя дождётся, пока снимут все остальные.

Так же работает кнопка «Отменить» в редакторе. Сначала она отменяет последнее действие, затем предпоследнее. Программе здесь нужен порядок, обратный порядку записи: что сохранено позже, то выдаётся раньше.

Такой порядок даёт обычный массив, если добавлять и забирать элементы только с его конца. Давайте посмотрим на историю действий редактора:

const history = [];
history.push("type");
history.push("bold");
history.push("delete");

console.log(history.pop()); // delete
console.log(history.pop()); // bold
console.log(history.join(" ")); // type

Разберём программу по строкам:

1. const history = [] создаёт пустую историю.
2. Три вызова push дописывают действия в конец массива: "type", "bold", "delete".
3. Первый pop снимает последнее действие и печатает delete.
4. Второй pop снимает bold.
5. history.join(" ") печатает то, что осталось: type.

Вершина стека

Стек — набор значений, в который добавляют и из которого забирают только с одного конца. Этот конец называют вершиной. Значение, положенное последним, забирают первым: «последним пришёл — первым ушёл».

В массиве вершина — его конец. Значение кладут на стек методом push и снимают методом pop: он удаляет последний элемент и возвращает его. Остальные элементы оба метода не трогают.

Здесь аналогия с тарелками заканчивается. Стопка сама не даёт взять нижнюю тарелку, а массив даёт: history[0] прочитает первый элемент. Стеком массив делает ваше правило трогать только конец.

Взгляд на вершину

Иногда на вершину нужно только посмотреть, не снимая её. Метод at возвращает элемент по индексу и понимает отрицательные индексы, которые отсчитывают от конца. Поэтому stack.at(-1) — последний элемент. Это то же, что stack[stack.length - 1], только короче.

const stack = [1, 2];
stack.push(3);
console.log(stack.at(-1), stack.length); // 3 3
console.log(stack.pop(), stack.at(-1)); // 3 2
console.log([].at(-1), [].pop()); // undefined undefined

Давайте разберём вывод:

1. После push(3) на вершине 3, а в стеке три элемента: строка печатает 3 3.
2. pop() снимает и возвращает 3, и вершиной становится 2: печатается 3 2.
3. У пустого массива вершины нет: at(-1) и pop() возвращают undefined, и ошибки нет.

Чтение at(-1) стек не меняет, как взгляд на верхнюю тарелку её не снимает. А pop укорачивает стек на один элемент.

Парные скобки

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

Проверка идёт по строке слева направо:

1. Открывающую скобку кладут на стек.
2. Закрывающая скобка должна составлять пару с вершиной, и тогда вершину снимают.
3. Когда строка кончилась, стек должен остаться пустым.

Для строки "([)]" шаги такие:

Закрывающая скобка без пары на вершине, в том числе на пустом стеке, означает ошибку. Если строка кончилась, а стек не пуст, какая-то скобка осталась незакрытой. Для "([])" проверка доходит до конца с пустым стеком: все скобки закрыты.

Частая ошибка

Вершину пытаются прочитать отрицательным индексом в квадратных скобках:

const stack = ["(", "["];
console.log(stack[-1]); // ✗

Ошибки нет, но программа печатает undefined. Квадратные скобки не отсчитывают индексы от конца: для них -1 — имя свойства, которого у массива нет. Метод at понимает отрицательный индекс, и stack.at(-1) возвращает "[".

Главное

• Стек отдаёт первым значение, положенное последним; в массиве его вершина — конец.
• push кладёт значение на вершину, а pop снимает его и возвращает.
• at(-1) читает вершину, не снимая её; у пустого стека и он, и pop возвращают undefined.
• В квадратных скобках отрицательный индекс не работает: stack[-1] даёт undefined.