Skip to main content

Стек - stack

Стек использует модель LIFO - last in first out.
В JavaScript нет специальной структуры данных стек. Ее роль тут играет массив. Это связано с тем, что JavaScript разрабатывался как язык с динамичной типизацией и упрощенным набором инструментов для более быстрой веб-разработки.
Однако, несмотря на отсутствие этой структуры как встроенных классов, в JavaScript легко реализовать стек, используя массивы благодаря их встроенным методам.

Example GIF

Классический стек — это абстрактная структура данных, которая предусматривает следующие операции:

  • Push: Добавление элемента на вершину стека.
  • Pop: Удаление и возврат элемента с вершины стека.
  • Top или Peek: Возвращение элемента на вершине стека без его удаления.
  • IsEmpty: Проверка стека на пустоту.
Big O
​
let stack = []; // вот этот массив будет нашим стеком
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
console.log(stack);

Загвоздка с массивами​

И тут возникает первая несостыковка - в классическом понимании стек и массив имеют разное время на доступ, поиск и вставку. Какое же время правильное, если мы используем массив?

Вопрос для вас - как вы думаете, почему у массива время доступа к элементу O(1)?

Решение загвоздки​

Для стека, реализованного с помощью массива в JavaScript:

  • Операции вставки (push) и удаления (pop) последнего элемента обычно имеют временную сложность O(1), так как эти операции производятся на конце массива и не требуют сдвига элементов.
  • Операция поиска (Search) будет иметь сложность O(n), так как может потребоваться просмотреть весь стек.
  • Операция доступа (Access) к произвольному элементу в стеке, если он не последний, также будет иметь сложность O(n), так как вам нужно снять верхние элементы, чтобы добраться до него.

Вопрос - какую сложность будет иметь операция доступа (Access) к последнему элементу массива?

Операции поиска и доступа к произвольному элементу не являются частью стандартного интерфейса стека. В классическом стеке предполагается, что вы не имеете прямого доступа к элементам в середине стека — вы работаете только с вершиной. Эти ограничения делают стек структурой данных типа LIFO (Last In, First Out).

Зачем нам вообще нужен стек?​

  • Стек часто используется как часть решения какого-то алгоритма, например, в рекурсиях или обходах деревьев (не думайте сейчас об этом много!).
  • Парсинг документов для понимания контекста.
  • Промисы и асинхронные функции в JavaScript используют стек вызовов и цикл событий для управления асинхронными операциями (это управление скрыто от разработчика).

Пример​

Рассмотрите код описанный ниже и попытайтесь ответить на вопрос - что выведет данный код в консоль и почему

let stack = [];
let lastValue = null;

function execute(value) {
  lastValue = value;
  stack.push(value);
}

function undo() {
  stack.pop();
  lastValue = stack[stack.length - 1] || null;
  return lastValue;
}

execute("write code");
execute("test code");
execute("commit code");
console.log(undo());
console.log(undo());
console.log(undo());