Понимание и реализация стеков

Что такое стеки?

Стеки - это способ структурировать данные. Они основаны на концепции LIFO (Last In First Out). Они могут быть реализованы различными способами (которые будут рассмотрены позже), но идея состоит в том, что у вас есть 2 способа взаимодействия с данными: подтолкнуть элемент вверху стека или удалить элемент из вершины стека.

Почему используются стеки?

Для обработки логики LIFO стеки имеют большое число:

  1. Вставка O (1)
  2. Удаление O (1)
  3. Найти элемент O (n)
  4. Элемент доступа O (n)

Они используются, потому что они почти мгновенно вставляют и удаляют элементы. В некоторых других структурах данных для обработки вставки требуется O (n), потому что сначала нужно найти, куда вы ее вставите (глядя на деревья двоичного поиска!). В других случаях, чтобы удалить, вам нужно найти элемент, который нужно удалить первым, или, как в Arrays, вам нужно переместить каждый элемент внутри.

Где используются стеки? Вы можете узнать некоторые из них.

  • JavaScript стек вызовов
  • Приложения, реализующие отмену / повтор
  • Приложения, которые включают недавно использованные
  • Любые данные, которые необходимо обрабатывать с помощью логики Last In First Out.
  • Программирование интервью - так что делайте заметки 👀

Массивы JavaScript как стеки

Вы можете обрабатывать стеки, используя массивы JavaScript. Хотя они немного медленнее, чем другие альтернативы, они уже реализованы в JavaScript. Работает полностью из коробки. Помните, что стеки должны реализовывать две вещи; они должны иметь возможность удалить последний элемент, добавленный в список, и иметь возможность добавить элемент в конец списка.

Вот два способа обработки стеков с помощью массивов:

  1. Вы можете использовать методы push и pop в Array (добавить в конец, удалить в конце)

2. Вы можете использовать методы unshift и shift Array (добавить в начало, удалить с начала).

Создание собственного стека со связанными списками

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

Реализация класса Node

Узел имеет два свойства: данные и следующее. Выглядит это так:

Реализация класса Stack

Стек имеет три свойства: первый узел, последний узел и длину стека. Выглядит это так:

Stack push и pop методы

Есть два способа обработки push и pop. Как и в случае с массивами, мы можем вставлять и удалять в конце связанного списка или в начале связанного списка.

Между ними есть огромные различия. Они здесь:

  1. Вставить и удалить в конце связанного списка (подумайте о методах Array push и pop)
  • Вставка O (1)
  • Удаление O (n)

2. Вставить и удалить в начале связанного списка (подумайте о методах Array unshift и shift).

  • Вставка O (1)
  • Удаление O (1)

Хотя обычно это называется push и pop, мы будем реализовывать его так, как если бы он был без сдвига и сдвига. Это потому, что если вы вставляете и удаляете в конце связного списка, удаление последнего узла требует итерации по всему стеку. Это потому, что вам нужно изменить последний элемент стека, чтобы он был предшествующим ему элементом. Поскольку у нас нет доступа к предыдущему списку со связанными списками, вам нужно перебрать весь стек, чтобы получить его.

При вставке и удалении в начале связанного списка не используются предыдущие элементы, а используются только следующие, к которым у нас есть доступ в связанных списках. Благодаря этому вставка и удаление происходят в постоянное время, достигая нашей цели O (1).

Реализация метода Stack push (unshift)

При добавлении элемента в стек необходимо обрабатывать два разных случая:

  1. Стек пуст.
  2. В стеке есть элементы.

В обоих случаях вам нужно создать новый узел с заданными данными и увеличить длину на единицу.

В коде push (unshift) выглядит примерно так:

Случай 1: когда стек пуст

Сделайте оба свойства first и last стека новым узлом.

Случай 2: когда в стеке есть элементы

Сделайте так, чтобы новый узел указывал на первое свойство стека, а затем измените первый на новый узел.

Реализация метода Stack pop (shift)

Есть три разных случая удаления элемента из стека:

  1. В стеке нет элементов.
  2. В стеке всего один элемент.
  3. В стеке есть несколько элементов.

В коде pop (shift) выглядит примерно так:

Случай 1: когда в стопке нет предметов

Ничего не делать и вернуть null.

Случай 2: когда в стеке только один элемент

Удалите узел, содержащий элемент, установив для обоих first и last значение NULL. Уменьшите длину стека на единицу и верните данные, которые были в удаленном узле.

Случай 3: когда в стеке несколько элементов

Удалите первый узел, установив первый элемент стека следующим элементом в списке. Уменьшите длину стека на единицу и верните данные, которые были в удаленном узле.

Полный код стека

В целом стек, реализованный со связанными списками, выглядит примерно так:

Спасибо, что зашли так далеко! Это было краткое руководство по стекам в JavaScript. Если вы нашли это полезным, оставьте аплодисменты. Если у вас есть идеи для будущих тем или вопросы, оставьте ответ ниже!