Стек

Тема алгоритмов не существует сама по себе. Важно не только уметь составлять правильный алгоритм решения, но не менее важно использовать для работы с данными правильную структуру.

Структура данных — это конкретный способ хранения и организации данных. В зависимости от решаемых задач, удобным оказывается либо один способ организации данных, либо другой. Как минимум, одну структуру данных вы уже знаете достаточно хорошо — это массив. С точки зрения организации, массив представляет собой совокупность элементов, к которым имеется индексированный доступ (доступ по индексу), а вот с точки зрения физического хранения в памяти — всё сложнее. Массивы бывают разные и внутри языка реализуются тоже по-разному.

Кроме массивов существует множество других структур данных, таких как списки, хеш-таблицы, деревья, графы, стек, очередь и другие. Использование структуры данных, подходящей под решаемую задачу, позволяет кардинально упростить код, устраняя запутанную логику.

Некоторые из перечисленных структур данных мы рассмотрим в процессе прохождения курсов и проектов, другие вам нужно будет подтянуть самостоятельно из книг. В любом случае алгоритмы и структуры данных (без фанатизма) составляют базу, на которую нанизывается всё остальное в разработке.

В этом уроке мы разберем один из самых простых и важных абстрактных типов данных – стек (stack, переводится как стопка).

Стек

Стек — упорядоченная коллекция элементов, в которой добавление новых и удаление старых элементов всегда происходит с одного конца коллекции. Обычно его называют вершиной стека.

Стек

У стека есть аналоги из реальной жизни. Например магазин автомата. Патроны добавляются в магазин только друг за другом. Извлекаются тоже, только в обратном порядке. Последний вставленный патрон выйдет из магазина первым.

Магазин

Практически любая стопка может рассматриваться как стек. Если не применять грубую физическую силу, то со стопками мы работаем двумя способами. Либо кладём новый элемент (например, книгу) на верхушку стопки, либо снимаем элемент с верхушки. Поэтому стек ещё называют "Last In First Out" (LIFO), то есть "последний зашёл, первый вышел".

Перед тем, как разбирать конкретную задачу, посмотрим на роль, которую играет стек в программировании. Вспомните, как исполняется любая программа. Одни функции вызывают другие, которые, в свою очередь, вызывают третьи, и так далее. После того, как выполнение заходит в самую глубокую функцию, та возвращает значение, и начинается обратный процесс. Сначала идёт выход из наиболее глубоких функций, затем из тех, что уровнем выше, и так далее до тех пор, пока не дойдёт до самой внешней функции. Вызов функций — не что иное, как добавление элемента в стек, а возврат – извлечение из стека. Именно так всё устроено на аппаратном уровне. К тому же, если в процессе выполнения программы происходит ошибка, то её вывод часто называют Stack Trace (трассировка стека).

Другой пример, связанный с программированием — кнопка "назад" в браузере. История посещений представляет собой стек, каждый новый переход по ссылке добавляет её в историю, а кнопка «назад» извлекает из стека последний элемент.

Работа со стеком включает в себя следующие операции:

  • Добавить в стек (push)
  • Взять из стека (pop)
  • Вернуть элемент с вершины стека без удаления (peek)
  • Проверить на пустоту (isEmpty)
  • Вернуть размер (size)

Первые две – базовые, остальные нужны время от времени. В JavaScript стек можно создать на основе массивов. Для этого используются методы push(), pop() и свойство length.

const stack = [];

stack.push(3);
console.log(stack); // => [ 3 ]
stack.push('Winterfall');
console.log(stack); // => [ 3, 'Winterfall' ]
stack.push(true);
console.log(stack); // => [ 3, 'Winterfall', true ]

const element1 = stack.pop();
console.log(element1); // => true
console.log(stack); // => [ 3, 'Winterfall' ]

const element2 = stack.pop();
console.log(element2); // => Winterfall
console.log(stack); // => [ 3 ]

https://repl.it/@hexlet/js-arrays-stack

Обратите внимание, что методы pop() и push() изменяют исходный массив. pop не только изменяет его, но и возвращает элемент, снятый со стека.

Рассмотрим задачку, решение которой тривиально при использовании стека. Кстати, её нередко задают на собеседованиях, как раз чтобы убедиться, хорошо ли вы знаете базовые структуры данных.

Задача:

Необходимо реализовать функцию, которая проверяет, что парные скобки сбалансированы. То есть каждая открывающая скобка имеет закрывающую: (), ((()())). А вот пример несбалансированных скобок: (, ((), )(. Для проверки баланса недостаточно считать количество, важен так же порядок в котором они идут.

У этой задачи есть простое решение и без стека, но стек тоже хорошо подходит (и даже нагляднее)

Решение со стеком выглядит так:

  1. Если перед нами открывающий элемент, то заносим его в стек
  2. Если закрывающий, то достаём из стека элемент (очевидно, последний добавленный) и смотрим, что он открывающий для данного закрывающего. Если проверка провалилась, значит выражение не соответствует требуемому формату.
  3. Если мы дошли до конца строки и стек пустой, то всё хорошо. Если в стеке остались элементы, то проверка не прошла. Такое может быть, если в начале строки были открывающие элементы, но в конце не было закрывающих.

Разберём его построчно:

const checkIfBalanced = (expression) => {
  // Инициализация стека
  const stack = [];
  // Проходим по каждому символу в строке 
  for (const symbol of expression) {
    // Смотрим открывающий или закрывающий
    if (symbol === '(') {
      stack.push(symbol);
    } else if (symbol === ')') {
      // Если для закрывающего не нашлось открывающего, значит баланса нет
      if (!stack.pop()) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

export default checkIfBalanced;

https://repl.it/@hexlet/js-arrays-stack-balancing

Предположим, что на вход функции попала следующая строка: ((). Ниже описание ключевых шагов при выполнении функции проверки:

  1. Первая скобка ( заносится в стек, так как она открывающая
  2. Следующая скобка ( также заносится в стек по той же самой причине
  3. Последняя ) является закрывающей, из стека извлекается последняя добавленная скобка
  4. В стеке остался один элемент, значит баланса нет

Семантика

Может возникнуть соблазн использовать эти функции в повседневной практике. Например, чтобы извлечь из массива последний элемент. Несмотря на то, что метод pop() действительно позволяет это сделать, такой вариант использования крайне нежелателен по нескольким причинам:

  1. Побочный эффект данной операции — изменение исходного массива. Даже если массив потом не используется, такой код вносит потенциальные проблемы и заставляет его переписывать в будущем.

  2. Нарушается семантика. Инструменты нужно использовать по назначению, иначе рождается код, который декларирует одно, но в реальности делает другое. Любой опытный программист, который видит pop() сразу считает, что массив в данной части программы используется как стек. Если это не так, то понадобятся дополнительные умственные усилия для понимания происходящего.

Для извлечения последнего элемента лучше использовать метод last() библиотеки lodash.


Дополнительные материалы

  1. метод push
  2. метод pop

Для полного доступа к курсу, нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам Хекслета, даст возможность обращаться за помощью к менторам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов

Зарегистрироваться

или войти в аккаунт

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг».