Простая реализация очереди на Ruby

Содержание

1. Ключевые характеристики:
2. Основные операции:
3. Использование
4. Реализация

В этом посте содержится информация из ChatGPT.

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

Очередь - это линейная и динамическая структура данных, работающая по принципу FIFO (First In, First Out). Это означает, что первый вошедший элемент первым и покинет очередь. Вспомните очередь людей в банке: первый в очереди получает обслуживание первым.

Ключевые характеристики:

Упорядоченное введение и удаление: Элементы добавляются в конец очереди и удаляются из ее начала.

Основные операции:

Enqueue: Добавление элемента в конец очереди, обновление хвостовой ссылки и обновление количества элементов.

Dequeue: Удаление элемента из начала очереди, обновление ссылки на голову и обновление количества элементов.

Peek/Front: Проверяет первый элемент очереди, не удаляя его.

Использование

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

Реализация: Может быть реализована с помощью массивов или связанных списков. Простота и эффективность очереди делают ее популярным выбором в различных программных приложениях.

Очереди, как и связанные списки, требуют контейнера для хранения данных в структуре, в данном случае - узлов.

Классическим примером использования очередей в разработке программного обеспечения является управление асинхронными задачами или сообщениями. Это особенно часто встречается в распределенных системах и веб-приложениях, где операции могут быть отложены и выполнены вне основного потока, чтобы избежать блокировки обработки.

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

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

Реализация

Эта реализация ориентирована не на производительность, а на простоту понимания.

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

class Node
  attr_accessor :value, :next_value

  def initialize(value)
    @value = value # Завернутые данные
    @next_value = nil # Ссылка на следующий начинается nil
  end
end

# Реализация очереди
class Queue
  attr_accessor :length, :head, :tail

  def initialize
    @length = 0
    @head = nil
    @tail = nil
  end

  def enqueue(value)
    node = Node.new(value) # Создание нового узла
    @length += 1 # Обновление длины очереди

    if @head.nil? # Проверяем, не является ли head nil
      @head = @tail = node # Устанавливаем новый узел в качестве head и tail
      return # Завершаем enqueue
    end

    @tail.next_value = node # Сохраняем ссылки
    @tail = node # Tail получает новый узел
  end

  def dequeue
    return nil if @head.nil? # Нечего декеировать

    @length -= 1 # Обновляем длину до -1
    head = @head # Сохраняем текущую голову в переменной
    @head = head.next_value # Обновляем голову до второго элемента
    # head.next_value = nil # Разрываем связь между старой головой
    # требуется в языках без GC

    head.value # Возвращаем удаленное значение
  end

  def peek
    return nil if @head.nil? # Повторная проверка, если head равен nil
    @head.value # Возвращает значение head
  end
end

# Всегда полезно иметь несколько автоматизированных тестов :)
require 'rspec/autorun'

describe '#enqueue / #dequeue / #peek' do
  it 'имеет значение Jose' do
    q = Queue.new
    q.enqueue('Jose')
    expect(q.peek).to eq('Jose')
    expect(q.length).to eq(1)
    q.enqueue('Mary')
    expect(q.peek).to eq('Jose')
    expect(q.length).to eq(2)
    q.dequeue
    expect(q.peek).to eq('Mary')
    expect(q.length).to eq(1)
  end
end

Надеюсь, вам понравится.