В этой статье мы собираемся погрузиться в создание стека, который является важной структурой данных. Его использование разнообразно, и важно знать, как работает структура данных стека, если вы хотите стать разработчиком полного стека.

Стек - это линейная структура данных, которая соответствует концепции Последний пришел - первый ушел (LIFO). Это означает, что первым удаляется последний элемент, вставленный в стек.

Говоря о линейной структуре данных в основном, это набор элементов данных, которые связаны друг с другом, так что элементы расположены последовательно, и каждый элемент связан со своим предыдущим и следующим элементом. Чтобы получить более полное представление о линейной структуре данных, посетите учебные пособия.

Чтобы сделать это руководство кратким и точным в отношении понимания реализации с использованием связанного списка, мы собираемся сосредоточиться на двух основных основных операциях стека: Push и Pop.

  • Push: используется для добавления элемента в коллекцию, а
  • Pop: удаляет из стека элемент, добавленный последним.

Помните, что первый элемент идет в конец стека, а последний элемент всегда находится вверху стека, что делает его готовым к операции pop.

ПОЗВОЛЬТЕ НАМ КОД

Я предполагаю, что у вас уже есть редактор кода и вы уже изучили основы javascript. Хорошо, создайте новый файл javascript (например, stack.js) и откройте его в редакторе кода.
В этом файле мы собираемся создать два класса. Класс Node, который будет определять наш текущий и следующий элемент. И класс Stack, который будет содержать два основных метода Push & Pop.

В приведенном выше фрагменте кода мы создали класс Node с конструктором. Конструктор принимает два параметра. top_param - это вершина стека, а next_param - элемент рядом с вершиной.

Пример: у нас есть номер 1 в качестве первого элемента в стеке, а следующий элемент 1 имеет значение NULL, потому что не существовало элемента до номера 1. Следовательно, номер 1 является текущей вершиной стека.
Позже, мы решаем добавить номер 2. Номер 1 будет сдвинут вниз, позволяя вставить номер 2. Теперь нашей вершине стека будет присвоен номер 2, потому что это вновь вставленный элемент, и он будет указывать на номер 1 в качестве своего следующего элемента. IE: 2 → 1 → null

Глядя на изображение выше, мы создаем новый класс под названием S tack, который будет содержать методы для наших операций. У этого класса также есть конструктор, который объявляет и инициализирует верхнюю часть стека как null по умолчанию.
Теперь давайте продолжим и определим первый метод, который может позволить нам помещать элементы в стек.

Хорошо, мы добавили метод push, но что он на самом деле делает? Чтобы упростить, метод принимает параметр, называемый элементом, после чего выполняются 4 шага, которые перечислены ниже.

  • Затем он создает параметр как новый элемент узла.
  • После создания мы отслеживаем наш текущий указатель, назначая ему вершину стека.
  • Затем мы устанавливаем наш текущий указатель как следующий элемент нашего вновь созданного узла.
  • Наконец, мы устанавливаем вершину стека как вновь созданный узел.

Теперь, когда наш метод push готов, перейдем к методу pop.

Приведенный выше фрагмент изображения является определением метода pop. Это довольно просто, правда? Хорошо, давайте разберемся.

  • Мы начинаем с отслеживания нашего текущего элемента в верхней части стека и присвоения его текущей переменной-указателю.
  • Во-вторых, мы обновляем верх стека, чтобы он стал следующим элементом текущего указателя.

Например:
2 → 1 → ноль. Номер 2 - это наша текущая вершина стека, поэтому следующий элемент после номера 2 - это номер 1. Поэтому мы устанавливаем номер 1 как нашу новую вершину стека.

  • Наконец, мы возвращаем удаленный элемент. В приведенном выше примере номер 2.

Запустим код

Теперь, когда мы успешно реализовали структуру данных стека с использованием связанного списка, давайте проверим, работает ли он!

Давайте быстро подведем итоги того, что мы сделали в приведенном выше фрагменте кода.

  • Сначала мы создаем экземпляр класса стека
  • Во второй и третьей строках мы обращаемся к методу push и добавляем два элемента 1 и 2.
  • Наконец, мы регистрируем всплывающий элемент, который в нашем примере имеет номер 2.

Заключение

Принцип структуры данных стека - последовательность последний пришел - первый ушел. Есть и другие операции, которые можно реализовать со стеком:

  • Push: добавление элемента в верхнюю часть стопки.
  • Pop: удаление элемента из верхней части стопки.
  • IsEmpty: проверьте, пуста ли стопка.
  • IsFull: проверьте, заполнен ли стек.
  • Peek: получите значение верхнего элемента, не удаляя его.

Этот учебник освещает только две основные операции. Вы можете попробовать изучить другие, чтобы получить больше информации.
Ниже приведен полный код, который мы только что реализовали. Вот и все, вот как создать стек, используя связанный список!