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

От автора: узнайте о двух важных структурах данных — стеке и очереди — и о том, как реализовать их в JavaScript.

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

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

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

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

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

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

Стек

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

Стек обычно представляет собой структуру последовательных и упорядоченных элементов, основанную на принципе «последний пришел — первым ушел» (LIFO). Вы можете возразить, что иногда можно удалить элемент из середины стека, не удаляя тарелку сверху, и это веский аргумент. Но иногда это решение может работать не так, как ожидалось. Представьте, что в некоторых ситуациях у нас есть возможность удалить только самый последний элемент, добавленный в стек.

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

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

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

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

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

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

let stack = [];

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

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).

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

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

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

JavaScript — очень удобный язык, который предоставляет нам множество различных методов, которые помогут нам достичь лучших результатов. Преимущество в 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;
}

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

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

Заключение

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

Автор: Leonardo Maldonado

Источник: www.telerik.com

Редакция: Команда webformyself.