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
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.
- You get in line.
- One by one the individuals at the front of the line are allowed on the ride.
- You follow the line and eventually it’s your turn and you get on the ride.
- 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
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.
In the study of algorithms, queues typically have two methods:
enqueue method adds items to the end of a queue data structure. This differs from the the
dequeue method which removes the first element.
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
scala> var batting_order = new Queue[String]
This will create an empty queue that we can work with and store it in the
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")
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:
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
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:
In the next guide we’ll walk through the
Stack data structure.