🔍

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

🗓️ 29 апреля 2020 г. 1 мин. чтения

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

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

myQueue = () => {
  const queue = []
  return {
    add(x) {
      queue.unshift(x)
    }
  }
}

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

myQueue = () => {
  const queue = []
  return {
    add(x) {
      queue.unshift(x)
    },
    remove() {
      return queue.pop()
    }
  }
}

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

const marvelMovies = myQueue()
marvelMovies.add('Iron Man')
marvelMovies.add('Captain America')

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

myQueue = () => {
  const queue = []
  return {
    add(x) {
      queue.unshift(x)
    },
    remove() {
      return queue.pop()
    },
    next() {
      return queue[queue.length - 1]
    },
    length() {
      return queue.length
    },
    empty() {
      return queue.length === 0
    }
  }
}
Copyright © 2020