Всем привет! Это вторая часть серии статей о структуре данных и алгоритмах в 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++;
    }

Поп

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

  1. Если стек пуст, вернуть undefined
  2. Если стек не пуст
  • Сохраните значение верхнего элемента, т.е. (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.