Стек и очередь в JavaScript

Простая статья рассказывающая о базовых структура данных знания о которых может пригодится например при прохождение собеседования на позицию веб программиста.

Перевод: Leonardo Maldonado — Stack and Queue in JavaScript

В статье кратко описываются две важные структуры данных — стек и очередь, и демонстрируется пример их реализации в JavaScript.

Каждый раз, когда мы разрабатываем новое приложение, есть определенные моменты, которые которые нужно обдумать заранее, чтобы достичь конечной цели и получить хороший результат. Например, это может быть моменты связанные с хранением данных, работа с логикой состояния, то как должна обрабатываться аутентификация и т. д.

Наверное, одним из самых важных моментов является хранение данных. Данные — важный аспект каждого приложения. От выбора способа хранения данных зависит работа всего приложения, его скорость и надежность. Поэтому так важен выбор типа структуры данных. Существуют разные структуры данных, у каждой свой вариант использования, но все они могут иметь одну и ту же цель — достижение максимальной производительности приложения при хранении и работе с данными.

Стек

Представьте, что вам нужно вымыть стопку тарелок после обеда с семьей. Как бы вы это начали? Что ж, очевидный ответ: сверху.

Так же и стек представляет собой структуру последовательных и упорядоченных элементов, основанную на принципе «последний пришел — первым ушел» (LIFO — last in first out).

Структура данных стека выполняет две основные операции:

1. push—Эта операция отвечает за вставку или перемещение нового элемента в стек.
2. pop—Эта операция отвечает за удаление самого последнего элемента из стека.

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

Иногда в структуре данных стека может быть более двух операций. Например, мы можем использовать операцию isEmpty, чтобы проверить, пуст ли стек, и операцию peek , чтобы вернуть верхний элемент без изменения стека.

Теперь, когда мы знаем, как работает структура данных стека, приступим к реализации на JavaScript.

Хорошая вещь в работе со стековыми структурами данных в JavaScript заключается в том, что JavaScript уже предоставляет нужные нам методы push и pop. Метод push добавляет элемент в массив, а метод pop удаляет последний элемент из массива.

Мы можем начать наш стек, создав новый массив с именем stack:

let stack = [];

Теперь мы можем создать нашу операцию push. Эта функция будет отвечать за получение элемента в качестве аргумента и добавление этого элемента в наш стек.

const push = (item) => stack.push(item);

Теперь мы создадим следующую операцию pop. Эта функция будет отвечать за удаление последнего элемента стека. По сути, это будет последний элемент, добавленный в стек. Поскольку мы не знаем, какой именно элемент может быть последним в стеке, эта функция не получает никаких аргументов.

const pop = () => stack.pop();

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

class Stack {
 constructor() {
   this.stack = [];
 }
 push(item) {
   this.stack.push(item);
 }
 pop() {
   this.stack.pop();
 }
}

Некоторым разработчикам нравится реализовывать стековые структуры данных с использованием связанных списков вместо массивов в JavaScript. Хотя это может показаться хорошим решением, его производительность может быть не самой лучшей.

Как здесь указал Хёнджэ Джун, производительность массивов в сравнение со связанными списками в стековых структурах данных намного выше.

В некоторых особых случаях связанные списки могут работать лучше, чем массивы, но при реализации структур данных стека в JavaScript всегда предпочтительнее массивы. Методы массива, которые мы использовали, push и pop, имеют сложность O (1), что означает, что они совершено не зависят от количества обрабатываемых данных и всегда будут иметь одинаковую производительность.

Очередь

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

Так же и очередь — это линейная структура последовательных и упорядоченных элементов, похожая на стек, с той разницей, что она работает по принципу «первым пришел — первым вышел» (FIFO — first in first out).

Структура данных очереди имеет две основные операции:

1. enqueue—Эта операция отвечает за вставку или отправку нового элемента в очередь.
2. dequeue—Эта операция отвечает за удаление первого элемента из очереди.

Как и случае со стеком в JavaScript есть уже готовый метод удаления первого элемента массива, которым является метод массива shift.

Благодаря этому реализация очереди в JavaScript становится очень простой и мощной. Мы можем определить наш массив очереди следующим образом:

let stack = [];

Теперь мы можем создать нашу операцию постановки в очередь, чтобы добавить элемент в нашу очередь, точно так же, как мы это сделали с примером стека. Создадим функцию с именем enqueue и передадим ей аргумент:

const enqueue = (item) => queue.push(item);

Теперь мы можем создать функцию для удаления первого элемента нашей очереди для этого создадим функцию dequeue.

const dequeue = () => queue.shift();

Все довольно просто.

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

Помните, что методы push и pop имеют сложность O(1)? Метод shift  имеет сложность O(n).

Простая разница в сложности (или как еще говорят О большого) может иметь определяющее значение для работы приложения. Если вы планируете работать со структурой данных очереди, лучший вариант — создать собственную очередь. Например так:

function Queue() {
  this.queue = {};
  this.tail = 0;
  this.head = 0;
}

// Add an element to the end of the queue.
Queue.prototype.enqueue = function(element) {
  this.queue[this.tail++] = element;
}

// Delete the first element of the queue.
Queue.prototype.dequeue = function() {
  if (this.tail === this.head)
      return undefined

  var element = this.queue[this.head];
  delete this.elements[this.head++];
  return element;
}

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

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

Заключение

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

Дополнение от переводчика

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

Эта куча (heap)

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

Здесь я приведу лишь простое объяснение структуры данных куча.

Куча — это такой вид дерева, у которого есть одно важное свойство: если узел A — это родитель узла B, то ключ узла A больше ключа узла B (или равен ему).

Лучше всего это можно увидеть на картинке.

Реализации кучи как структуры данных в JavaScript совсем не так просто как стека и очереди. Более подробно это рассмотрено например в этой статье.