Освоение структур данных в Ruby — Очереди

Очереди — это особый вид связанные списки что позволяет вам обрабатывать коллекцию элементов переменного размера в порядке поступления (FIFO). Как и все структуры данных, которые мы видели до сих пор; очереди — это просто последовательности соединенных узлов.

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

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

Вот как будет выглядеть очередь, содержащая два элемента:

[1 | next] -> [2 | next] -> X (nil)

Теперь предположим, что мы хотим сохранить новый элемент:

[1 | next] -> [2 | next] -> [3 | next] -> X (nil)

И теперь мы хотим удалить один:

[2 | next] -> [3 | next] -> X (nil)

Обратите внимание, как очереди растут к хвосту и сжимаются с головы.

Интерфейс очередей

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

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

Детали реализации

Каждый элемент в очереди представлен узлом, который содержит два атрибута:

• Значение, которое содержит текущий узел.
• Указатель на следующий узел в очереди.

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

Далее следует краткое описание каждого метода, его сложности и исходного кода.

Инициализировать

Этот метод является конструктором очереди. Он создает пустую очередь, устанавливает головной узел в nil и длину очереди в 0.

Сложность этого метода составляет O(1).

def initialize
  self.head = nil
  self.length = 0
end

поставить в очередь

Создает новый узел для вставки значения в очередь. Если в очереди нет узлов, новый узел становится головным; в противном случае он добавляется в конец очереди.

Поскольку очередь хранит указатели на свою голову и хвост, сложность этого метода составляет O(1).

def enqueue data
  node = Node.new data
  unless head
    self.head = node
  else
    self.tail.next = node
  end
  self.tail = node
  self.length += 1
end

Удалить из очереди

Удаляет элемент из очереди. В отличие от того, что происходит в обычных связанных списках, удаление в очередях происходит просто, потому что они всегда происходят в начале очереди.

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

def dequeue
  return nil unless self.length > 0
  self.head = self.head.next
  self.tail = nil if self.length == 1
  self.length -= 1
end

заглянуть

Возвращает узел, находящийся в начале очереди, не удаляя его, или nil, если очередь пуста.

Поскольку dequeue не возвращает удаляемый элемент, просмотр — это путь, если вам нужно что-то сделать с этим элементом.

Сложность этого метода составляет O(1).

def peek
  self.head
end

чистый

Удаляет все элементы из очереди.

def clear
  while self.peek
    dequeue
  end
end

Каждый

Этот метод проходит по очереди, выдавая по одному элементу за раз, пока не достигнет последнего элемента.

Из-за семантики очередей я не очень люблю такие методы, как этот, но должен признать, что время от времени они могут пригодиться. (т. е. во время выполнения сеансов отладки.)

Сложность получения следующего элемента в очереди составляет O (1). Сложность получения всей очереди составляет O(n).

def each
  return nil unless block_given?
  current = self.head
  while current
    yield current
    current = current.next
  end
end

Распечатать

Распечатайте содержимое очереди, пройдя ее элементы.

Сложность этого метода составляет O(n).

def print
  if self.length == 0
    puts "empty"
  else
    self.each { |node| puts node.data }
  end
end

Когда использовать очереди

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

Регистрация на конференции, системы онлайн-продаж и диспетчеры событий — все это хорошо подходит для очередей.

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

Итак, это все об очередях. Я надеюсь, что вам понравилось!

В следующий раз, Стэкс. Следите за обновлениями!

PS: если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии бесплатно на вашем устройстве Kindle.

Структуры данных с нуля — Ruby Edition.