Understanding the Queue Data Structure – a Guide for Developers

0
548

In the world of algorithms you won’t make it far without a clear understanding of how the queue data structure works. In this guide to the queue data structure we’ll walk through:

  • What a queue is
  • What they’re used for

Lastly we’ll finish up by taking a practical look at how queues can be used in real world development.

Abstract Data Structures

Even though a number of languages, including Ruby and Scala, have a Queue class, typically queues are considered abstract data structures. This means that they are used to help explain algorithms and processes, but are rarely used in applications.

With that being said it is still important to learn how queues work, especially if you are going an algorithm course.

Queues In the Real World

queue data structure

Thankfully there is an easy way to understand how queues work in the real world, and to see them in action we get to take a trip to disneyland.

The workflow for going on a ride at Disneyland is pretty straightforward.

  1. You get in line.
  2. One by one the individuals at the front of the line are allowed on the ride.
  3. You follow the line and eventually it’s your turn and you get on the ride.
  4. When you’re on the ride you are no longer in the line.

In this example the Disneyland line is the queue and you are an element in the queue. Much like our amusement park line Queues are made up of elements and have a strict way that the elements need to behave.

Queue Data Flow

Looking at the data flow for this data structure, queues follow what’s called a First In First Out (FIFO) type of data flow. This means that if you place the following items into the queue:

4, 2, 4, 6, 1, 2, 6

The first 4 will be the first element allowed to leave the queue. This type of behavior differs from the Array data structure that allows any element to be removed. Much like the Disneyland example, queues don’t allow for cutting in line.

Queue Methods

In the study of algorithms, queues typically have two methods:

  • Enqueue
  • Dequeue

The enqueue method adds items to the end of a queue data structure. This differs from the the dequeue method which removes the first element.

Practical Implementation

Let’s see how the Scala programming language works with the Queue data structure. If you have Scala installed on your system you can run this code in the terminal by typing scala which will open up a scala terminal session. (You can download Scala from here).

We’re going to build a small batting order program that takes a list of baseball players and then runs through the lineup, just like in a real baseball game.

Creating a Queue

We’ll begin by creating a new queue called batting_order:

scala> var batting_order = new Queue[String]

This will create an empty queue that we can work with and store it in the batting_order variable.

Using Enqueue

Now let’s use the enqueue method to add values to the queue.

We can add players one at a time like this:

scala> batting_order += "Springer"

Or we can add multiple elements at the same time:

scala> batting_order += ("Bregman", "Altuve")

Using Dequeue

With our batting order complete with three elements, what happens each time a player comes to the plate? That’s where the dequeue process comes in. If we run the following code:
batting_order.dequeue

Running the program returns Springer because he was the first one we added to the batting_order queue. If we run it again it will return Bregman.

Summary of Queue Data Structure

And that’s it! The Queue data structure is quite straightforward, which is part of its strength. Whenever you hear someone referencing a queue you’ll know that the data structure uses a First In First Out data flow and that it has two key methods: enqueue and dequeue.

What’s Next?

In the next guide we’ll walk through the Stack data structure.

Resources

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here