Easy Queue implementation in Ruby
Tags: ruby, datastructures, algorithms, programming
Published: 2023-11-21 15:21:01

_This post contains some info from the ChatGPT._

You might think, "Queues aren't used much in Ruby," and it's true, you don't often see a queue implementation in Ruby or Rails projects. But for me, the time has passed when I cared about whether I'll use something in my career or not. I just want to have the knowledge, and I advise you reading this post to do the same, you'll never know when you're going to need it and I believe these things are what make a big difference in our career.

The Queue is a linear and dynamic data structure, following the FIFO (First In, First Out) principle. This means the first element to enter is the first to leave. Think of a line of people at a bank: the first one in line gets served first.

### Key characteristics:

**Ordered insertion and removal:** Elements are added at the end of the queue and removed from the beginning.

### Basic operations:

- Enqueue: Add an element at the end of the queue, update the tail reference, and update the item count.

- Dequeue: Remove the element from the beginning of the queue, update the head reference, and update the item count.

- Peek/Front: Check out the first element of the queue without removing it.

### Usage

Ideal for situations requiring processing in the order of arrival, such as resource management in computing or customer service. 

Implementation: Can be implemented with arrays or linked lists. The simplicity and efficiency of the Queue make it a popular choice in various software applications.

Queues, like Linked Lists, require a container to hold the data within the structure, in this case, Nodes.

A classic example of using queues in software development is managing asynchronous tasks or messages. This is especially common in distributed systems and web applications, where operations can be deferred and executed outside the main flow to avoid blocking processing.

For example, in an e-commerce application, when a user places an order, the order confirmation and payment processing might be added to a queue. Meanwhile, the user gets an immediate response that their order has been received. In the background, services processing payments and updating inventory consume these tasks from the queue, processing them sequentially.

This allows the application to handle demand spikes more efficiently, spreading the workload over time, and ensuring that critical operations are completed reliably and in order.

### Implementation

This implementation is not focused on performance, but on being easy to understand.

```ruby

# One of the smallest data structures we can have,
# a simple Node acting like a container to wrap our data.

class Node
  attr_accessor :value, :next_value

  def initialize(value)
    @value = value            # Wrapped data
    @next_value = nil         # Reference to next starts nil    
  end
end

# The Queue implementation

class Queue
  attr_accessor :length, :head, :tail

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

  def enqueue(value)
    node = Node.new(value)  # Create a new node
    @length += 1            # Update the Queue length 

    if @head.nil?           # Check if head is nil
      @head = @tail = node  # Set the new node as head and tail
      return                # ends the enqueue
    end

    @tail.next_value = node # Keeping the references
    @tail = node            # Tail receives the new node
  end

  def dequeue
    return nil if head.nil? # Nothing to dequeue

    @length -= 1            # Update length to -1

    head = @head            # Save current head in a variable
    @head = head.next_value # Update head to the second item

    # head.next_value = nil # Breaks link between the old head
                            # required in non GC languages

    head.value              # Return the removed value
  end

  def peek
    return nil if head.nil? # Checking again if head is nil

    head.value              # Returns the head value
  end
end

# Always a good idea having some automated tests :)

require 'rspec/autorun'

describe '#enqueue / #dequeue / #peek' do
  it 'has the Jose value' 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
```

Hope you like it.