От автора: узнайте о двух важных структурах данных — стеке и очереди — и о том, как реализовать их в JavaScript.
Каждый раз, когда мы разрабатываем новое приложение, есть определенные темы, которые мы должны продумать в первую очередь, чтобы достичь нашей цели и получить хороший результат. Как мы собираемся хранить данные, как мы будем работать с логикой состояния, как мы должны обрабатывать аутентификацию и т.д.
Наверное, одним из самых важных является то, как хранить данные. Данные — важный аспект каждого приложения. Так мы можем узнать больше о наших пользователях. Они рассчитывают, что мы будем хранить их данные, и мы должны тщательно выполнять эту работу.
Мы можем воспринимать структуры данных как эффективный способ хранения. Существуют разные структуры данных, каждая имеет свой вариант использования, но все они должны иметь одну и ту же цель — добиться максимальной производительности при хранении и работе с ними.
Мы используем структуры данных во всех аспектах компьютерного программирования, в нашем программном обеспечении, приложениях, веб-сайтах, интерфейсах командной строки, графическом интерфейсе пользователя и т.д. Каждая компьютерная программа имеет структуру данных.
В структурах данных хорошо то, что как алгоритмы структуры данных не зависят от какого-либо конкретного языка или фреймворка. Вот почему они — одна из самых важных концепций, которые должен знать разработчик. Каждый может понять и узнать о них, даже те, кто не является разработчиками.
Понимание того, как работают структуры данных, поможет вам лучше продумать код и то, как структурировать лучшие решения для задач. У каждой задачи есть разные возможные решения, которые мы могли бы использовать; не все проблемы решаются одинаково.
Стек
Представьте, что у вас есть стопка тарелок, которую нужно вымыть после обеда с семьей, и вы обязаны вымыть ее. С чего бы вы начали? Что ж, очевидный ответ: сверху.
Стек обычно представляет собой структуру последовательных и упорядоченных элементов, основанную на принципе «последний пришел — первым ушел» (LIFO). Вы можете возразить, что иногда можно удалить элемент из середины стека, не удаляя тарелку сверху, и это веский аргумент. Но иногда это решение может работать не так, как ожидалось. Представьте, что в некоторых ситуациях у нас есть возможность удалить только самый последний элемент, добавленный в стек.
Поисковик Apple будет оценивать сайты по силе их влияния
Структура данных стека следует тому же принципу и называется структурой данных LIFO. LIFO означает «последним пришел — первым ушел», точно так же, как работает стопка тарелок или другие типы стопки в реальном мире — последний элемент, добавленный в стопку, должен быть первым.
Структура данных стека выполняет две основные операции:
push — эта операция отвечает за вставку или перемещение нового элемента в стек.
pop — эта операция отвечает за удаление самого последнего элемента из стека.
Стек — это линейная структура данных, что означает, что все элементы расположены в последовательном порядке. В результате операции push и pop могут происходить только на одном конце структуры, в данном случае на вершине стека.
Иногда в структуре данных стека может быть более двух операций. Иногда мы можем использовать операцию isEmpty, чтобы проверить, пуст ли стек, и операцию просмотра, чтобы вернуть верхний элемент без изменения стека.
Теперь, когда мы знаем, как работает структура данных стека, приступим к реализации на JavaScript.
Положительным в работе со структурами стека данных в JavaScript является то, что JavaScript уже предоставляет нам методы push и pop, которые мы обсуждали. Метод push добавляет элемент в массив, а метод pop удаляет последний элемент из массива.
Мы можем начать наш стек, создав новый массив с именем stack:
JavaScript let stack = [];
Теперь мы можем создать операцию push. Эта функция будет отвечать за получение элемента в качестве аргумента и добавление элемента в наш stack.
JavaScript const push = (item) => stack.push(item);
| 1 | const push = (item) => stack.push(item); |
Теперь мы создадим еще одну операцию с именем pop. Эта функция будет отвечать за удаление последнего элемента стека. По сути, это будет последний элемент, добавленный в стек. Поскольку мы не знаем точно, какой элемент может быть последним в стеке, то функция не получает никаких аргументов.
JavaScript const pop = () => stack.pop();
| 1 | const pop = () => stack.pop(); |
Мы также можем реализовать структуру данных стека в JavaScript с помощью классов. Вот как мы можем это сделать:
JavaScript class Stack { constructor() { this.stack = []; } push(item) { this.stack.push(item); } pop() { this.stack.pop(); }
}
| 1234567891011 | class Stack { constructor() { this.stack = []; } push(item) { this.stack.push(item); } pop() { this.stack.pop(); }} |
Инструмент Search Console для переиндексации страниц снова заработал
Некоторым разработчикам нравится реализовывать стековые структуры данных с использованием связанных списков вместо массивов в JavaScript. Хотя это может показаться умным решением, производительность может быть не самой лучшей.
Как Хьюнджей Джун отметил здесь, производительность массивов в сравнении со связанными списками в структурах данных стека лучше.
В некоторых конкретных случаях связанные списки могут работать лучше, чем массивы, но при реализации структур данных стека в JavaScript всегда предпочтительнее массивы. Методы массива, которые вы собираетесь использовать, push и pop, будут иметь временную сложность O(1), что означает, что они будут работать эффективно и будут иметь наилучшую возможную производительность.
Очередь
Представьте себе, что у нас есть очередь людей, которые хотят войти в конкретный ресторан. Последний человек в очереди будет последним, кто войдет в ресторан, в зависимости от размера очереди. Первый человек, который встанет в очередь, будет первым, кто войдет в ресторан.
Очередь — это линейная структура последовательных и упорядоченных элементов, похожая на стек, с той разницей, что она работает по принципу «первым пришел — первым вышел» (FIFO).
Структура данных очереди называется структурой данных FIFO: это структура последовательно упорядоченных элементов, в которой первый удаляемый элемент будет первым элементом, добавленным в очередь.
Структура данных очереди имеет две основные операции:
enqueue — эта операция отвечает за вставку или отправку нового элемента в очередь.
dequeue — эта операция отвечает за удаление самого старого элемента из очереди.
Подобно стеку, у нас есть линейная структура данных, что означает, что все операции в очереди могут происходить только на одном конце структуры, в данном случае в начале очереди.
JavaScript — очень удобный язык, который предоставляет нам множество различных методов, которые помогут нам достичь лучших результатов. Преимущество в JavaScript заключается в том, что у нас также есть метод удаления первого элемента массива, которым является метод массива shift.
Реализация очереди в JavaScript становится очень простой и мощной. Мы можем определить наш массив очередей следующим образом:
JavaScript let stack = [];
Теперь мы можем создать операцию постановки в очередь, чтобы добавить элемент в очередь, точно так же, как мы это сделали с примером стека. Создайте вызываемую функцию enqueue и передайте ей аргумент, например:
JavaScript const enqueue = (item) => queue.push(item);
| 1 | const enqueue = (item) => queue.push(item); |
Теперь мы можем создать функцию для удаления первого элемента нашей очереди. Мы создадим функцию с именем, dequeue и эта функция будет отвечать за удаление первого элемента нашей очереди.
JavaScript const dequeue = () => queue.shift();
| 1 | const dequeue = () => queue.shift(); |
Довольно просто, да? Но есть некоторые скрытые различия, которые мы можем сначала не заметить, особенно в производительности.
Помните, что такие методы как push и pop имеют временную сложность O(1)? Метод shift имеет временную сложность O(N).
Простая разница во временной сложности фрагмента кода может иметь большое значение для затрат и производительности. Если вы планируете работать со структурой данных очереди, лучше всего создать собственную очередь.
JavaScript 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;
}