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

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

Стеки

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

Это называется LIFO - последний пришел, первый ушел. Мы также можем описать это как FILO - первым пришел, последний ушел.

Сценарии использования стеков

Стеки очень важны в движках, зависящих от языка. Возможно, вы слышали о переполнении стека при написании плохого кода.

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

Еще один полезный способ использования стеков - это история браузера.

Мы переходим с одного веб-сайта на другой, сохраняя посещаемость стопки веб-страниц. Последняя посещенная веб-страница будет в верхней части стека. Когда мы нажимаем кнопку «Назад» или «Вперед», мы можем использовать верхнюю часть стека.

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

Операции в стеке

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

  1. Pop (элемент вверху стопки) - O(1)
  2. Push (элемент вверху стопки) - O(1)
  3. Подглядывать (см. верхнюю часть) - O(1)

Обычно мы все равно не хотим использовать стек для поиска, Big-O для поиска в стеке будет O(N), где N - длина стека.

Реализуйте стек в JavaScript

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

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

Как вы думаете, какая структура данных лучше всего подходит для стека?

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

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

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

Это компромисс при выборе между массивами и связанными списками. Но оба они обеспечат постоянную временную сложность для операций со стеками и очередями. Давайте посмотрим на это в действии.

Реализация стека с использованием связанного списка в JavaScript

Мы знаем, что связанный список содержит узлы - каждый узел имеет значение this.value и ссылку на следующий узел this.next. У нас есть ссылка на начало связанного списка this.top и конец списка this.bottom.

Для каждой операции мы будем использовать операции связанных списков - prepend для push и remove с индексом 0 для pop.

  1. Peek: возвращает значение node, на которое указывает this.top.
  2. Push: создайте новый node и добавьте его вверху связанного списка.
  3. Pop: удалить первый элемент в связанном списке.

Реализация стека с использованием массива в JavaScript

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

Очереди

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

Это называется FIFO - первым пришел - первым ушел. Мы также можем сказать это как LILO - последний пришел, последний ушел.

Примеры использования очередей

Мы можем использовать очередь в

  • приложение лист ожидания для покупки билетов
  • бронирование мест для приложения в ресторане
  • что-то вроде Uber, где мы заказываем поездки
  • принтер - первый запрос будет напечатан первым

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

Операции в очереди

Мы видим, что в очереди мы хотим просмотреть и выбрать первый элемент. Но мы хотим поместить элемент в конец очереди. Эти операции будут иметь линейную временную сложность.

  1. Поставить в очередь (поместить элемент в конец очереди) - O(1)
  2. Удалить из очереди (вывести первый элемент в очереди) - O(1)
  3. Peek (первый элемент) - O(1)

Обычно мы еще не выполняем поиск в очереди, Big-O для поиска в очереди будет O(N), где N - длина очереди.

Реализовать очередь в JavaScript

Снова давайте рассмотрим, что у нас есть массивы и связанные списки, и, поскольку у нас нет очередей, реализованных непосредственно в JavaScript, какая структура данных, по вашему мнению, лучше всего подходит для очереди?

Для очередей нам нужен первый элемент как для постановки в очередь, так и для удаления из очереди. Если мы используем связанные списки, то сложность по времени для добавления и удаления первого элемента будет O(1). Рассмотрим следующий связанный список A --> B --> C.

Head                    Tail
 A    ----   B    ----   C

Если мы хотим удалить A или добавить в начале, мы меняем указатель для головы и следующего узла.

Находясь в массивах, нам придется сдвинуть оставшиеся элементы в массиве, что является O(N) операцией.

0  1  2       Remove A       0  1 
A  B  C   -----------------  B  C

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

Реализация очереди с использованием связанного списка в JavaScript

Для каждого элемента мы создаем новый node и имеем две ссылки this.first и this.last в качестве ссылки на начало и конец связанного списка.

  1. Peek: возвращает значение node, на которое указывает this.first.
  2. Поставить в очередь: создать новый node и добавить его в конец связанного списка.
  3. Dequeue: удалить первый элемент в связанном списке.

Почему и когда - стопки или очереди

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

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

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

✅ Быстрый доступ (Вверху стека или первым в очереди)

✅ Fast Peek (Вверху стека или первым в очереди)

✅ По порядку (верх стека или конец очереди)

❌ Медленный поиск

Ссылки и дополнительная литература

  1. Структура данных с помощью JavaScript
  2. DS с JS - массивы
  3. DS с JS - Связанные списки