Структура данных — Реализация стека в Javascript

Эта статья посвящена реализации структуры данных стека в javascript с нуля.

Полный код приведен в конце статьи. Сначала мы упростим все операции со стеком до небольших лаконичных функций, а затем объединим все функции в конце.

Что такое стек?

Стек — это тип структуры данных, который следует принципу LIFO — Last In First Out.

Элемент, добавленный в стек последним, будет удален первым.

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

Стеки обычно используются для функций отмены и повтора.

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

Мы должны иметь возможность инициализировать стек с помощью

const stack = new Stack();

и мы должны иметь возможность хранить в нем данные.

Давайте сначала начнем с создания класса стека

class Stack {
  constructor(){
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

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

Далее давайте определим класс для каждого узла стека.

class Node {
  constructor(value){
    this.value = value;
    this.next = null;
  }
}

Объяснение. Приведенный выше узел будет хранить часть данных в this.value и ссылаться на следующий узел в this.next.

Теперь, двигаясь дальше, в стеке push и pop являются постоянными, так как мы добавляем или удаляем последний вставленный элемент в стеке.

Реализация Push() для стека

Для помещения в стек нам нужно позаботиться о следующих случаях:

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

push(val){
    var newNode = new Node(val);
    <!-- if there are no nodes in the stack -->
    if(!this.first){
      this.first = newNode;
      this.last = newNode;
    }else {
      <!-- if the stack already has nodes -->
      var temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    <!-- keeping track of size -->
    return ++this.size;
  }

Реализация Pop() для стека

Случаи, которые нам необходимо рассмотреть

• если стек пуст, вернуть ноль
• если есть только один узел, первый и последний станут нулевыми после того, как мы удалим узел
• если более 1 узла, текущий первый -> следующий становится первым
• следить за размером стека

pop(){
    <!-- if no nodes in the stack -->
    if(!this.first){
      return null;
    }
    let temp = this.first;
    <!-- If only one node -->
    if(this.first === this.last){
      this.last = null;
    }
    <!-- if more than one node -->
    this.first = this.first.next;
    this.size--;

    return temp;
  }

Полный код для реализации стека в JS

class Node {
constructor(value){
  this.value = value;
  this.next = null;
}
}
class Stack {
constructor(){
  this.first = null;
  this.last = null;
  this.size = 0;
}
push(val){
  var newNode = new Node(val);
  if(!this.first){
    this.first = newNode;
    this.last = newNode;
  }else {
    var temp = this.first;
    this.first = newNode;
    this.first.next = temp;
  }
  return ++this.size;
}
pop(){
  if(!this.first) return null;
  var temp = this.first;
  if(this.first === this.last){
    this.last = null;
  }
  this.first =  this.first.next;
  this.size--;
  return temp.value;
}
}

var stack = new Stack();
console.log(stack.push(10));
console.log(stack.push(40));
console.log(stack.push(411));
console.log(stack.push(50));
console.log(stack.pop());
console.log(stack.pop());