The Rambling Programmer

Queues

Data Structures & Algorithms

Last week we discussed stacks, the LIFO, data structure that allows us to push and pop elements onto and from it. This week we cover queues, the stack’s partner in crime.

While a stack is a Last In First Out data structure, if this doesn’t make sense to you see last weeks article, Stacks. A queue on the other hand is a First In First Out, or FIFO. This simply means that the first element to be placed in the queue is the first one to leave. In other words it’s a line.

Hurry up and wait.

So a stack has two essential methods. The “enqueue”, or place an element at the back of the line, and the “dequeue”, or remove element from the front of the line. Let’s look at an image to solidify this.

Pretty simple, right? So, lets get our hands dirty and create an implementation in Ruby.

Much like the stack we implemented in the last blog, Ruby makes implementing a queue trivial. The below implementation of a queue is really unnecessary, but for the sake of learning, is valuable.

class Queue
  def initialize
    @queue = []
  end

  def enqueue(item)
    @queue.push(item)
  end

  def dequeue
    @queue.shift
  end
end

That’s really it. Like I said above, this implementation is purely academic, serving no real purpose other than to learn how a queue works. Ruby gives us the array methods to mimic a queue without having to create the above queue class.

So now that we understand how queues work, let us consider where queues work. Anytime you need a first come, first served type of interaction, a queue is suitable.

Consider a web server that serves files to hundreds, if not thousands of users at a time. All of these users cannot be serviced at the same time, so we put the requests in line, using a queue, and serve them in the order the requests were placed. Another example is at a hardware level. A processor cannot run all processes asked of it at the same time, instead we queue up the processes and run them in order.

These are just two examples. I’m sure, with little effort, you can imagine many more. Thanks for reading along, until next week, consider the links below.

Wikipedia - Queue

Wikipedia - FIFO