Mastering data structures in Ruby — Queues

Queues are a special kind of linked lists that allows you to handle a variable-sized collection of elements in first in first out fashion (FIFO). As well as all of the data structures we have seen so far; queues are just sequences of connected nodes.

The differentiating factor for queues is that the order of retrievals is guaranteed to be first in first out.

Contrary to what happens with the other lists we have seen; queues won’t allow us to insert/remove elements at random locations. All elements are inserted at the head of the queue and removed from its tail.

This is how a queue that holds two elements would look like:

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

Now let’s say we want to store a new element:

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

And now we want to remove one:

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

Notice how queues grow to their tail and shrink from their head.

Queues interface

In comparison with other list alike data structures, the interface for queues is quite simple because they had few operations.

While you can add helper methods like find_first or cat, I think that those methods dim the semantics of this data structure and that is why I ‘ve decided to leave them out.

Implementation details

Each element on the queue is represented by a node that contains two attributes:

• The value that the current node holds.
• A pointer to the next node in the queue.

The first node of the queue is called head and the last one tail. To mark the end of the queue we must set the next pointer of the last element to nil.

What follows is a brief description of each method, its complexity and source code.

Initialize

This method is the queue constructor. It creates an empty queue, sets the head node to nil and the queue’s length to 0.

The complexity of this method is O(1).

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

Enqueue

Creates a new node to insert a value into the queue. If the queue has no nodes, the new node becomes the head of the queue; otherwise, it’s appended at the tail of the queue.

Since the queue keeps pointers to its head and its tail, the complexity of this method is 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

Dequeue

Removes an element from the queue. In contrast to what happens on regular linked lists, removals on queues are straightforward because they always happen at the head of the queue.

To remove an element from the queue, we point the head to the node that it’s next to it and set tail to nil if the queue contains just one element.

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

Peek

Returns the node that’s at the head of the queue without removing it or nil if the queue is empty.

Since dequeue doesn’t return the element that’s being removed, peek is the way to go if you have to do something with that element.

The complexity of this method is O(1).

def peek
  self.head
end

Clear

Dequeues all elements from the queue.

def clear
  while self.peek
    dequeue
  end
end

Each

This method walks the queue yielding one at a time until it reaches the last element.

Because of the semantics of queues, I’m not a big fan of having methods like this one on them, but I’ve to admit that from time to time they might be handy. (i.e., while running debugging sessions.)

The complexity to yield the next item in the queue is O(1). The complexity to yield the whole queue is O(n).

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

Print

Print the contents of the queue by walking its items.

The complexity of this method is O(n).

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

When to use queues

Queues work well in those cases where you need to handle elements in first come first served basis.

Conference registrations, online selling systems, and event dispatchers are all good fits for queues.

As it happens with other data structures we have seen so far; queues work great for a relatively small variable-sized collection of data. If you have to handle millions of elements, you will have to wait until we get to “advance data structures” in this series.

So, that’s it for queues. I hope you enjoyed it!

Next time, Stacks. Stay tuned!

PS: If you are a member of the Kindle Unlimited program, you can read a bit polished version of this series for free on your Kindle device.

Data Structures From Scratch — Ruby Edition.