Стеки и очереди — одна из многих примитивных структур данных. И это хорошая отправная точка, если вы хотите изучить структуры данных. В этой статье мы поговорим о стеках, их фактической реализации и, конечно же, о реализации на языке JavaScript.

Стеки — это динамические наборы, в которых заранее задан элемент, удаляемый из набора операцией DELETE . В стеке элемент, удаленный из набора, является последним вставленным: стек реализует политику «последним пришел — первым вышел» или LIFO . Вы можете думать о стопке как о контейнере с любимыми чипсами, такими как Pringles или Lays.

Когда вы наполняете контейнер чипсами на производстве, вы начинаете есть с последнего чипа, помещенного в контейнер, а не с первого. Это один из многих реальных примеров политики или стека LIFO . Вы также можете думать о печенье или монетах, размещенных друг на друге.

Предположим, у нас есть n элементов.

Изначально стек имеет верхний параметр. Top показывает место последнего элемента в нашем стеке.

В этом примере вершина нашего стека равна 6, потому что 6-й элемент — последний элемент стека. Если бы у нас не было 9, то вершина нашего стека была бы 5 (5-й элемент — последний элемент стека). Когда мы пытаемся добавить элемент в заполненный стек, происходит переполнение стека. Но когда мы пытаемся вытолкнуть элемент из пустого стека, произойдет потеря значимости стека.

Когда в стеке n элементов, то он заполнен, как в нашем примере. Приступим к созданию стека.

Инициализировать стек

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

1. Сам стек (this.stackList)
2. Максимальная длина стека (this.maxLength, необязательно)
3. Вершина вашего стека (this.topIndex)

Пустой стек

Операция с пустым стеком проверяет, пуст стек или нет.

Толкать

Операция push добавляет один элемент в конец стека.

Поп

Операция pop извлекает (удаляет) последний элемент стека.

Дополнения

Я также добавил некоторые другие вспомогательные методы (операции), чтобы пользователь мог получить больше информации о своем стеке.

Проверьте длину стека

Проверьте сам стек

Проверить верхний параметр стека

Резюме

Итак, что мы имеем в итоге? У нас есть стек, который похож на массив с методами push, pop и length, но с большей функциональностью и эффективностью с точки зрения использования памяти.

Я думаю, что следующей структурой данных, которую мы рассмотрим, является структура данных очереди , в которой скрыта более интересная логика.

Кроме того, вы можете найти полный код, перейдя сюда .

Спасибо за прочтение, скоро увидимся

Другие темы структуры данных, которые я рассмотрел:

Односвязный список

Кэш LRU