December 31, 2017 · Computer Science Data Structures

Queue as a Line of People

A good metaphor for a queue is... *drumroll* a line of people, duh! Imagine you bought tickets to see your favorite band in concert, and it's the night of the concert. As you walk up to the venue, you see a long line of people on the sidewalk. You know you need to get in line. So where do you queue up? At the front of the line? Right smack dab in the middle of the line? Or how about choosing any old random spot and queueing up there? Nope, nope, and nope. Of course you have to park yourself at the end of line like everyone else, so that's exactly what you do.

line of people

Now that you've successfully gotten in line, you see the gatekeepers starting to let people in. Perfect timing! But who do they let in first? Do they let you in first? You? The last person in line who just got here a second ago? No of course not! They let in the first person in line, some crazy bloke who probably camped out on the sidewalk hours ago. They then let in the second person in line, then the third person in line, then the fourth person in line, ... etc. until finally they get to you! And this process goes on until everyone has finally gotten into the concert venue.

Okay, maybe that analogy was really obvious. Scratch that, it was really obvious. But that's really all there is to queues. The good news is that queues are quite similar to stacks, which we've already covered. So we'll go through the same steps as last time in order to cover queues as a data structure.

Queues Defined

A queue is another abstract data type defined by these two very simple rules:

  1. You can only insert at the end of the queue.
  2. You can only delete from the beginning of the queue.

These operations are usually called "enqueueing" and "dequeueing" from the queue. You can oftentimes also "peek" at a queue, or read its frontmost value. And you'll most likely also be able to check if the queue is empty.

In the concert venue example, each concertgoer "enqueued" themselves at the end of the line. And once they started letting people in, the gatekeepers "dequeued" each person from the front of the line one-by-one until everyone was let in.

Queues implemented

But how is a queue to be implemented? Since a queue is an abstract data type, there's nothing in the definition of the queue itself that tells us how we should implement it.

A slight problem

We could implement a queue as an array or as a simple linked list. But there's a bit of a problem with this. Remember that both arrays and linked lists boast O(1) inserts and deletes in their respective best-case scenarios. But in their respective worst-case scenarios, inserts and deletes are O(N). For arrays, it's O(1) to add or delete at the end. But its O(N) to add or delete at the beginning. And for linked lists, it's O(1) to add or delete at the beginning. But it's O(N) to add or delete at the end.

linked_list_bottleneck

This is problematic because with a queue, we want to insert at the end and delete at the beginning. It would be ideal if both of these operations could be done in O(1) time. Right now, if we use an array, we can get O(1) enqueueing and O(N) dequeueing. And if we use a simple linked list, we can get O(N) enqueueing and O(1) dequeueing. But what we really want is O(1) enqueueing and O(1) dequeueing.

The solution

So what to do? The solution is to make a slight modification to our simple linked list. In its most basic implementation, we only retain a reference to the head node of a linked list. But we can also retain a reference to the tail node of the linked list as well. With direct access to the tail node, we no longer need to traverse through each and every node in order to get to the tail node. We can now get there in one step, which means we can insert and delete at the end of a linked list in O(1) time!

linked_list_mod

So if we implement a queue with this slightly modified version of a simple linked list, we can achieve both O(1) enqueueing and O(1) dequeueing! And indeed, queues are usually implemented as a linked list. We just need to keep a reference to both the head node and the tail node.

A Restricted Data Type

Just like with the stack, it's easy to be thrown by just how simple a queue really is. But you can think of a queue simply as a linked list with a very restricted API. There will be many scenarios in which all you need to do is add to the end of a collection and remove from the beginning. And in those cases, it really is nice if all those operations can be done in O(1) time.

And just like with the stack, the restrictive nature of a queue very elegantly models certain real-world scenarios perfectly. For instance, what do you think happens when you upload your own video to YouTube? YouTube doesn't process the video the second it receives it on their end. Video uploads are a very expensive operation and YouTube is getting a ton of uploads every second. Most likely, your video is going to be put onto a queue on YouTube's end. Eventually, your video will get to the front of the queue. And only then will your upload be processed by YouTube.

That's it!

I hope this post helps you understand queues better. With many of these data structures, don't be afraid to implement your own version of them from scratch. It's usually not as hard to do as it sounds, and you'll learn a ton. And get excited for next time, as we'll talk about the all-mighty hash as a data structure.