Продолжая свой путь программирования, я сосредоточился на том, чтобы больше узнать о структурах данных. Недавно я более подробно остановился на очередях и их реализации. Использование термина «очередь» на таких платформах, как Youtube, определенно увеличило мое любопытство как нового программиста. Подобно другим структурам данных, очередь - это просто набор данных, образующий линейную структуру. С точки зрения бухгалтерского учета он следует принципу FIFO (First In First Out). Элементы могут быть добавлены только в конец очереди и доступны только после того, как они окажутся впереди. Когда добавляются другие элементы, они становятся все более доступными.

Как и связанные списки и стеки, по сравнению с другими популярными структурами данных очереди, как известно, имеют отличное время выполнения для вставки и удаления. Чтобы действительно углубить свое понимание, я решил, что создание класса очереди в JavaScript будет лучшим способом действий. Очередь также может быть создана как массив, используя методы «push» и «shift» или «unshift» и «pop», но в этой статье я использовал другой подход. Как и многие другие структуры данных, очереди состоят из нескольких узловых элементов. Каждый узел содержит свойство «значение» и «следующее». Прежде чем мы приступим к созданию очереди, мы начнем с создания нашего класса Node. Хотя я создаю класс Node, в качестве альтернативы мы могли бы просто создать объект позже в нашем методе постановки в очередь. Но, тем не менее, вот наш базовый класс Node:

Чтобы начать работу с нашим классом Queue, как и со всеми другими классами в JavaScript, мы начнем с создания метода конструктора. Первичные элементы, к которым нам нужно получить доступ в нашей очереди, - это свойства first, last и length. Итак, в методе конструктора мы можем начать с установки наших first и last равными null, поскольку у нас еще нет доступных элементов. Затем для свойства length класса можно установить значение 0, пока мы не начнем добавлять элементы. Наш метод конструктора должен выглядеть так:

Двигаясь дальше, мы можем приступить к реализации основных методов нашего класса очереди. Стандартная очередь имеет три метода: просмотр, постановка в очередь и удаление из очереди. Наш метод peek будет просматривать узел, который находится в начале нашей очереди. Поскольку в очереди мы можем добавлять элементы только назад, наш метод enqueue справится с этим. Наконец, наш последний метод dequeue удалит наш первый элемент из очереди и вернет его. Чтобы полностью понять, что мы пытаемся сделать, подумайте о пользовательском опыте на Youtube. Пользователь может запустить очередь, добавить видео в очередь, и они будут воспроизводиться в том порядке, в котором они были добавлены. Вы также можете думать об очереди как о очереди в парке развлечений. Мы стоим в очереди, чтобы покататься, и наша позиция медленно перемещается вверх, пока мы, наконец, не дойдем до передней части и не сможем сесть на аттракцион.

Чтобы приступить к реализации этих методов, мы начнем с самого простого - peek. Наш метод просмотра, как описано выше, будет смотреть на наш список и отображать элемент, который находится следующим или перед строкой. Это можно сделать с помощью одной строчки кода «return this.first». Это вернет первый элемент в нашей очереди.

Теперь мы можем перейти к методам, которые фактически изменяют элементы в нашей очереди. Мы начнем с нашего метода постановки в очередь для добавления элементов. Этот метод будет принимать значение элемента, который мы добавляем в коллекцию данных. С этим значением мы создадим переменную (newNode), в которой будет установлен новый экземпляр нашего класса Node. Значение этого узла будет аргументом нашей инициализации. После того, как мы создали наш узел, мы должны проверить текущую длину очереди, чтобы увидеть, где он должен быть размещен. Если текущее свойство length по-прежнему равно 0, то мы знаем, что наш newNode будет нашим единственным элементом. В этом случае мы можем назначить его первым и последним элементом очереди. Если у нас есть значение длины, отличное от 0, то мы знаем, что у нас есть другие элементы. Если у нас есть другие элементы, мы назначим наш newNode «следующему» значению очередей текущего последнего элемента, поместив его в конец очереди. После того, как мы добавили наш узел, мы должны обновить наш последний элемент очереди, чтобы правильно отразить этот новый узел. Независимо от результата операторов if, мы закончим этот метод, увеличив длину и вернув очередь.

Продолжая, мы можем завершить наш класс Queue, реализовав метод dequeue. Этот метод просмотрит первый элемент в нашей «строке» и удалит его из коллекции. Для этого мы должны сначала проверить, есть ли в очереди элементы, которые мы действительно можем изменить. Мы можем сделать это, выполнив условие, чтобы проверить, есть ли у нас первый узел в нашей очереди. Если нет, мы можем просто вернуть null и завершить выполнение, так как удалять нечего. Затем мы проверим, есть ли в нашей очереди только один элемент. В этом случае мы должны удалить как первый элемент, так и последний элемент. Мы можем сделать это, проверив, равен ли первый элемент последнему. Если это так, мы должны присвоить нашему последнему элементу значение null. При желании мы можем сохранить наш текущий первый удаляемый элемент, установив его равным переменной holdingPointer. Это позволит нам вернуть значение удаленных узлов, если мы хотим, вместо того, чтобы возвращать нашу обновленную очередь. Наконец, мы можем обновить наш первый элемент очереди, чтобы он стал равным «first.next». Это удалит его из памяти очереди. В случае, если на самом деле в очереди был только один элемент и нет следующего значения, это установит для нового первого элемента значение NULL. Если в очереди есть несколько элементов, это присвоит значение за нашим первым элементом, чтобы оно было равно следующему элементу в списке, перемещая второй узел на передний план. Затем, как и в случае с нашим методом постановки в очередь, мы изменим длину. Мы уменьшим его на единицу и вернем значение нашей переменной holdingPointer, которое было удалено.

Создание очереди с нуля в JavaScript определенно было хорошим упражнением для лучшего понимания ее функциональности и возможных реализаций. Пока что это не было особо распространенным явлением на моем пути к программированию, но определенно является полезной структурой данных, которую стоит рассмотреть в дальнейшем. Благодаря функциям вставки и удаления, поддерживающим наилучшее / наихудшее время выполнения O (1) в очереди без массива, он определенно имеет свои преимущества. Очередь очень похожа на связанный список, но с двумя разными правилами.

  1. Вы не можете добавить элемент в начало «списка».
  2. Вы можете просматривать и удалять элементы только в начале этого «списка».

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