Алгоритмы и структуры данных в JavaScript — Очереди

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

Чтобы создать структуру данных очереди, давайте использовать фабричную функцию, которая возвращает очередь в виде объекта JavaScript. Внутри этой функции мы инициализируем пустой массив с именем queue. Очередь, которую мы создаем, также будет иметь различные свойства и методы внутри нее. Начнем с метода, который добавляет элементы в очередь только с одной стороны.

Здесь add() использует метод unshift для добавления элемента x в начало массива queue. Теперь нам нужно написать функцию, которая удаляет последний элемент из массива.

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

Теперь в соответствии с обычным поведением массива мы должны иметь элемент Iron Man с индексом 0, а Captain America — с индексом 1. Но поскольку marvelMovies — это очередь, Iron Man изначально был с индексом 0, и когда Captain America был добавлен в очередь, Iron Man был перемещен в индекс 1, а Captain America теперь находится в индексе 0. Удалить элементы из очереди просто. Все, что мы здесь делаем, это берем последний элемент в queue и извлекаем его.при помощи метода pop. Давайте добавим некоторую дополнительную функциональность в функцию, чтобы проверить следующий удаляемый элемент, длину очереди и, если очередь пуста или нет.

Сортировка пузырьком (bubble sort) на javascript

Bubble Sort является одним из наиболее широко обсуждаемых алгоритмов, просто из-за недостаточной эффективности сортировки массивов. Если массив уже отсортирован, Bubble Sort будет проходить через массив только один раз (с использованием концепции два ниже), однако в худшем случае это время выполнения O(n²), которое крайне неэффективно.

Когда мы рисуем скорость роста O(n²), мы видим, что по сравнению с другими алгоритмами сортировки, такими как сортировка слиянием, то есть O(n log n), он растет гораздо быстрее.

Не смотря на неэффективность Bubble Sort, все еще важно понять алгоритм и понять, почему он так плох.

Давайте углубимся в две концепции кодирования Bubble Sort.

Концепция 1

  • Итерация по массиву и проверка каждого элемента по следующему элементу в массиве.
  • Если текущий элемент больше, чем следующий элемент, меняйте их местами.
  • Если он не больше, переместите указатели вверх и сравните следующие два элемента.
  • Как только мы достигаем конца массива, мы знаем, что самый большой элемент находится в последней позиции.
  • Повторите этот процесс N раз, где N — длина массива, и каждый раз повторяйте до последнего отсортированного элемента.
Визуализация концепции 1

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

Концепция 2

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

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

Заключение

Bubble Sort — это один из самых неэффективных алгоритмов сортировки. В худшем случае нам придется сравнивать каждый элемент с каждым другим элементом в массиве, следовательно, сложность алгоритма будет O(n²).