Всем привет! Это вторая часть серии статей о структуре данных и алгоритмах в JavaScript. Ранее я объяснял Массив. В этом блоге я расскажу о стеке.
Что такое стек?
Стек — это линейная структура данных, которая следует определенному порядку выполнения операций. Порядок может быть следующим: LIFO (последним пришел — первым ушел) или FILO (первым пришел — последним ушел).— geeksforgeeks.org
Реальный мир, например. стопки может быть стопка книг, где книги располагаются одна над другой, книги можно добавлять или удалять из верхней части стопки книг
Список доступных операций
- Push: вставка элемента в стек.
- Pop: удаление элемента из стека.
- Peek: возвращает верхний элемент стека.
- Размер: возвращаемый размер стека.
- isEmpty: проверить, пуст ли стек, если пустой, вернуть true, иначе false.
- Очистить: сброс стека.
Реализация стека в JavaScript
Есть два способа, которыми стек может быть реализован в javascript: один из них — с использованием массива или с использованием объекта javascript. Поскольку у Array уже есть метод push для вставки элемента в конец массива, метод pop для удаления элемента и получения длины массива, у него есть свойство length который возвращает размер массива, если длина равна нулю, то массив пуст. вы можете получить реализацию массива стека здесь
Реализация стека с использованием объектов JavaScript
давайте определим стек имени ES6 class с двумя свойствами: count, который будет отслеживать количество элементов в стеке, и >items — объект, в котором будут храниться элементы. Ключ объекта Items будет инкрементным свойством счетчика и значением в качестве хранилища элементов в нем.
class Stack {
constructor() {
this.count = 0;
this.items = {};
}
}
Толкать
Чтобы добавить элемент в стек, мы будем использовать свойство count в качестве ключа для объекта items и элемент в качестве значения. После помещения элемента в стек мы увеличим свойство count на единицу. мы можем добавлять новые элементы только в верхнюю часть стека, то есть в конец стека
push(element) {
this.items[this.count] = element;
this.count++;
}
Поп
При удалении элемента из стека возможны два случая:
- Если стек пуст, вернуть undefined
- Если стек не пуст
- Сохраните значение верхнего элемента, т.е. (count -1)
- уменьшить значение свойства count на единицу
- удалить элемент из объекта items и вернуть сохраненное значение.
Поскольку в стеке используется принцип LIFO, последний элемент, который мы добавляем, удаляется
pop() { if (this.isEmpty()) { return undefined; } let result = this.items[this.count-1]; this.count --; delete this.items[this.count];
return result; }
заглянуть
Если стек пуст, верните undefined, иначе верните элемент Top, т.е. (count -1)
peek() {
if (this.isEmpty()) { return undefined; } return this.items[this.count-1]; }
Размер
Возвращает свойство count, которое отслеживает количество элементов в стеке.
size() {
return this.count;
}
пусто
Возвращает boolean, если свойство count равно нулю, то да true, иначе false.
isEmpty() {
return this.count == 0;
}
Прозрачный
Мы можем сбросить его до того же значения, которое мы определили в методе конструктора класса.
clear() {
this.items = {};
this.count = 0;
return this.items;
}
Или мы могли бы также извлекать элемент из стека, пока он не станет пустым.
while (!this.isEmpty()) {
this.pop();
}
полный исходник можно получить здесь
Вывод :
Стек — это структура данных, использующая принцип LIFO (Last In First Out). Мы можем вставить или удалить элемент только из вершины стека
Стеки имеют множество применений в реальных задачах. Их можно использовать для поиска проблем с возвратом, чтобы запомнить задачи или посещенные пути, а также для отмены действий.
Итак, следите за обновлениями в следующем блоге, в котором я расскажу о другой DS Queue.