Реализация стека в JavaScript

Структуры данных JavaScript

Тип абстрактных данных стека - это линейная структура данных. Он следует принципу «последний пришел - первым ушел» (LIFO). Элементы можно вставлять или удалять только с одного конца стека, то есть сверху. Последний элемент, который будет вставлен в стек, будет удален из него первым.

Когда верхний элемент стека удаляется, если стек остается непустым, то элемент сразу под предыдущим верхним элементом становится новым верхним элементом стека.

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

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

class Stack {
  constructor() {
    this.stack = [];
  }
  push(ele) {
    this.stack.push(ele);
    return this.stack;
  }
  pop() {
    return this.stack.pop();
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  size() {
    return this.stack.length;
  }
  isEmpty() {
    return this.stack.length === 0;
  }
}

• push ( item ) добавляет новый элемент в начало стопки. Ему нужно добавить элемент в стек.
• pop () удаляет верхний элемент из стека. Он не требует параметров и возвращает элемент. Стек изменен.
• peek () возвращает верхний элемент из стека, но не удаляет его. Думайте об этом, как о подсмотре ценности главного предмета.
• isEmpty () проверяет, пуст ли стек. Он не требует параметров и возвращает логическое значение; истина, если стек пуст.
• size () возвращает количество элементов в стопке. Он не требует параметров и возвращает целое число.
• Stack () создает новую пустую стопку. Он не требует параметров и возвращает пустой стек.

Переменная s ниже ссылается на новый класс Stack выше. Отсюда ‘s’ имеет доступ ко всем методам, определенным в классе Stack.

const s = new Stack();
s.size()            // 0
s.isEmpty()         // true
s.push(1)           // [ 1 ]
s.push(2)           // [ 1, 2 ]
s.pop()             // 2
s.peek()            // 1
s.isEmpty()         // false
s                   // Stack { stack: [ 1 ] }

Использование стека:

• Стек вызовов - это стек, который отслеживает вызовы функций в программе. Когда функция возвращается, к какой функции мы «возвращаемся»? Последний, который «подтолкнул» вызов функции.
• Поиск в глубину использует стек (иногда стек вызовов), чтобы отслеживать, какие узлы посещать следующим.
• Анализ строки - стеки могут быть полезны для нескольких типов синтаксического анализа строк. Перевернуть строку или проверить пару круглых скобок - распространенные вопросы на собеседовании.

Реализация:

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

Все операции со стеком выполняются быстро и эффективно. Требуется O (1) временная сложность и O (n) пространственная сложность.