Queues in Ruby

Interviews

Created by Stan on 09-04-2023

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the first element added to the queue will be the first one to be removed. Queues are frequently used in various applications, including task scheduling, handling requests in web servers, and implementing breadth-first search algorithms.

In this article, we will explore the concept of queues and learn how to implement and use them in Ruby. We will discuss key queue operations, create a custom queue class, and explore practical use cases for queues in Ruby.

A queue supports four primary operations:

  • enqueue: Add an element to the end of the queue.
  • dequeue: Remove the front element from the queue.
  • front: View the front element without removing it.
  • is_empty?: Check if the queue is empty.

Implementing a queue in Ruby

Ruby does not have a built-in queue data structure, but its Array class can easily be used as one. Here's a simple implementation of a Queue class using Ruby's Array:

class Queue
  def initialize
    @elements = []
  end

  def enqueue(element)
    @elements.push(element)
  end

  def dequeue
    @elements.shift
  end

  def front
    @elements.first
  end

  def is_empty?
    @elements.empty?
  end

  def size
    @elements.size
  end
end

Example usage of queues

1. Task scheduling

Queues can be used to manage a list of tasks to be executed in a specific order. Here's a simple Ruby program that simulates a task scheduler using a queue:

class Task
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def execute
    puts "Executing task: #{@name}"
  end
end

task_queue = Queue.new
task_queue.enqueue(Task.new("Task 1"))
task_queue.enqueue(Task.new("Task 2"))
task_queue.enqueue(Task.new("Task 3"))

until task_queue.is_empty?
  current_task = task_queue.dequeue
  current_task.execute
end

2. Breadth-first Search

Queues are often used to implement breadth-first search algorithms for traversing graphs or trees. Here's a simple example of using a queue for breadth-first search in a binary tree:

require_relative 'queue'

class Node
  attr_accessor :left, :right, :value

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

def breadth_first_search(root, target)
  return nil if root.nil?

  queue = Queue.new
  queue.enqueue(root)

  while !queue.is_empty?
    current_node = queue.dequeue

    return current_node if current_node.value == target

    queue.enqueue(current_node.left) if current_node.left
    queue.enqueue(current_node.right) if current_node.right
  end

  nil
end

# Create a binary tree
root = Node.new(10)
root.left = Node.new(5)
root.right = Node.new(15)
root.left.left = Node.new(3)
root.left.right = Node.new(7)
root.right.left = Node.new(12)
root.right.right = Node.new(17)

# Call breadth_first_search and print the results
target = 7
result = breadth_first_search(root, target)
if result
  puts "Found target #{target}: #{result.value}"
else
  puts "Target #{target} not found in the tree."
end

target = 20
result = breadth_first_search(root, target)
if result
  puts "Found target #{target}: #{result.value}"
else
  puts "Target #{target} not found in the tree."
end

3. Web server request handling

Queues can be used to manage incoming requests in a web server and process them in a FIFO order. Here's a simplified example of using a queue for request handling in a Ruby web server:

require 'socket'
require_relative 'queue'

class Request
  attr_reader :client

  def initialize(client)
    @client = client
  end 

  def process
    request = @client.gets
    puts "Processing request: #{request}"
    response = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\nHello, World!"
    @client.puts response
    @client.close
  end
end

server = TCPServer.new('localhost', 3000)
puts "Server started on port 3000"
request_queue = Queue.new

Thread.new do
  loop do
    client = server.accept
    request_queue.enqueue(Request.new(client))
  end
end

loop do
  unless request_queue.is_empty?
    current_request = request_queue.dequeue
    current_request.process
  end
end

In this example, we create a basic web server using Ruby's built-in socket library. We use a separate thread to accept incoming client connections and enqueue them into the request queue. The main loop then dequeues and processes requests in a FIFO order.

queue node ruby algorithm server socket binary_tree breadth_first_search bfs bst

Related Posts

Interviews

Posted on 08 Apr, 2023
Linked list in Ruby

Interviews

Posted on 09 Apr, 2023
Hash tables / hash maps in Ruby

Interviews

Posted on 01 May, 2023
Roadmap for the code newbie / aspiring junior developer