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.
# 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.
Top comments (0)