In the previous chapter, we learned about the Stack data structure. We will be talking about javascript queues in this post. The difference between a stack and a queue is the way items are added and removed. While items in a stack are LIFO collections, items in a queue are FIFO (First In First Out). A queue returns items in the same order it way added. The first to get in, is the first out! Lets see how this relates to the real world. Think of a grocery store or the bank cashier for example. The people who join the line, checkout out in the order they got in. If you are in line first, you get served first. If you are last in line, you are served last. Anyone who enters the bank goes to the back of the line (in queue). The same applies when you tell a printer to print a document. The items to print are queued, and are printed on a first come first serve bases. In software development, queues are used in multi threading and concurrency situations, where tasks that are waiting to be processed, are executed in an order of FIFO.  

Lets take a look at a diagram

In figure A in diagram above, we see a queue collection (a container with data). When we add data into our queue (in this case people), we perform an operation known as enqueue. So we enqueued Kofi, Tarik and Julia, where Kofi is in the front of the line (the head of the queue). Because of this he gets served by the bank teller first. When Kofi’s transaction with the cashier is done, he is removed from the queue so the next in queue can be helped. This remove operation is known as dequeue. He is dequeued from the collection (see figure B). Finally Tarik is now in the front of the line (the new head). This operation continues until the queue is empty. We can repeat the process by adding more data to the queue. Very simple to understand.

Now we can simulate other real world queue behavior. We can implement priority queues (queues that do not follow a FIFO order). In stead of removing the first in line, we remove items based on priority. Its like going to a an emergency room. Even if you got there an hour ago, someone (Patient Z) with a more severe injury that came in 5 minutes ago has priority over you (and goes first in line). And if another patient with that same severity comes in, then they would have to go in queue (behind Patient Z). We also have circular queues, where the first in line isn’t dequeued, however they are sent to the back of the line (Hot potato game anyone?).

So why is this idea of queues important? And where can we use queues in real world applications? As we saw earlier, we use queues to build printing like functionality. Cases where we would like to simulate people or things having to wait to use a resource (disk scheduling, printer, cpu scheduling). We can use javascript queues to implement sorting algorithms like radix sort as well. Since we are javascript developers, its important to know that the event loop uses a callback queue mechanism behind the scene. On the queue, callbacks are lined up and executed in the order in which they came in (provide nothing is running on the call stack).

Queue Implementation

Javascript queues can be implemented using an array or linked list as its backend data store. In the previous post on stacks, we used an array over a linked list, and i mentioned why we were doing that. We will be using an array again. However note that it is actually harder to use arrays in other languages to implement a queue! We should consider ourselves lucky because javascript as a language has made it so. It has methods that easily allows us to add data to the end of the array (enqueue), and methods to remove from the beginning of the array(shift). We also don’t have the “problem” is initializing an array with a set number of items as other languages do. This makes writing a queue in other languages much more difficult. For example what happens when you enqueue items and the array size is full? In javascript this does not happen, you can keep adding items at your hearts content. But in other languages you will need to allocate a longer array and copy the items to it before you can keep adding (there are actually other operations you have to perform, but i wont mention them here so we can focus on javascript). We could have also used a linked list with no problems (though arrays would still give you a better advantage). If you decide to use a linked list, then you should use the add to tail method to enqueue to the collection, and remove head method to dequeue (seen linked list post for more details).

The Queue Class

Lets write a basic queue class

See the Pen Queue class shell by kofi (@scriptonian) on CodePen.

Simple! We create a class with one property: items, which will be used to store our collection items. Lets create the ES2015 version

See the Pen RgjMMb by kofi (@scriptonian) on CodePen.

Now we will implement the queue helper classes.

Queue Operations

We talked about enqueue and dequeue as operations that happen within a queue collection. These are the main operations, however will we implement other methods that help make working with javascript queues easy. We will implement a front operation to help us see who is in front. A back operation to see who is last in line. Like the stack class we will implement size and isEmpty as well. We will also have a toString method to display all the elements in the queue. Lets add this to our class

See the Pen Queue Operations Shell by kofi (@scriptonian) on CodePen.

and here is the ES2015 version

See the Pen Queue Operations Shell – ES2015 by kofi (@scriptonian) on CodePen.

Here we have all the helper methods we need to make our queue function properly. Please download the queue.js file from the github repo. Lets implement the main queue operations

enqueue() & dequeue()

Lets update these methods in our code base

See the Pen Enqueue & Dequeue by kofi (@scriptonian) on CodePen.

And the ES2015 version

See the Pen Enqueue & Dequeue – ES2015 by kofi (@scriptonian) on CodePen.

Try not to get bored with this super simple code. Enqueue just adds an item to the queue. All we are doing is pushing onto the array. Dequeue removes the first item in the array. We use the shift method in the array.

front(), back(), empty() and toString()

Lets complete our other operations.

See the Pen Queue Class – front(), back(), empty() and toString() by kofi (@scriptonian) on CodePen.

and the ES2015 counterpart

See the Pen Queue Class – front(), back(), empty() and toString() –ES2015 by kofi (@scriptonian) on CodePen.

I have already explain what all of these are doing, so no need to go there again. They are all self explanatory.

Using the Queue class

Whew! Finally we can use our queue class. Lets create a queue at the bank. We will add the 3 users like we did in our diagram using enqueue and we will dequeue a user. We will console log to see what the looking looks like after performing some operations.

Lets look at what is going on here. We create a queue and added 3 people to it. We can see in (1) that there are 3 items in the array. Then we dequeue the line (meaning we remove from the beginning of the array). Since our dequeue method returns the element being dequeued, “kofi” is returned to us; leaving us with two users (3). When we check who is now in the front of the line (4) we get Tarik. And the back of the line is “Julia”. When we output everyone in the line, we have only two users, “Tarik” and “Julia”. Just like we would expect. Lets upgrade our queue.

Priority Queues

Lets get a more “real world”, where the first come first serve model (FIFO) is not always the case, even though there is a queue! We have all been there. For example when you are at the hospital, and someone with a more severe illness is brought in. They are seen first by the doctor. And what about airports! Isn’t there priority seating when its time to board the airplane? First class passages are seated first, followed by business class and finally we are last to board since we are flying coach (can you relate? i can!).  The same thing happens at the night club. Everyone is in line and those are are willing to get a table get seated right away! Unless of course there are no more tables. But, even those that want a table have to get in line if there are others also waiting for a table.

We can define a priority queue as one where items are added or removed not in a FIFO order, but rather based on some kind of priority constraints. Lets implement a priority queue. It looks very similar to the queue we have build, the only difference now is the data we put in the items array will now be an object. This object will have the element name as well as the priority code or number. Lets create our initial classes

See the Pen Priority Queue Classes by kofi (@scriptonian) on CodePen.

And the ES2015 version

See the Pen Priority Queue Classes – ES2015 by kofi (@scriptonian) on CodePen.

Lets take a closer look at our class. Notice we have two now. Not much has changed with our PriorityQueue class, however now we pass and extra parameter to the enqueue method ( priority ). When you decide to enqueue an element to the queue you have to pass a number which indicates the priority level. The higher the number, the higher the priority. We also have a QueueItem class which is actually what we will be pushing to the items array in our queue. It acts as an object containing the item name and priority values for each item. We could have easily created an object literal for this, but defining a class makes it even more clear that you are passing in a queue item object. Now lets finish up the class. We will be redefining our enqueue method since it now has to account for priority and insert the insert to the head/front of the queue. We will also re-write our toString method (everything else will be the same). Here we go

See the Pen Priority Queue – Enqueue & toString methods by kofi (@scriptonian) on CodePen.

And the ES2015 version

See the Pen Priority Queue – Enqueue & toString methods ES2015 by kofi (@scriptonian) on CodePen.

Lets see what enqueue is doing. When we call enqueue, we pass it two parameters. These are then passed to our QueueItem object and then ultimately pushed onto the items array in the PriorityQueue class. When we create a QueueItem object we run a for loop that iterates over all the elements in the items array(if there are any). For each item in the items arrays we check to see if the priority of the new item we want to add is greater than the current object’s priority in the iteration cycle. If its greater, we use the arrays splice method to insert the new object in that location/index. If the current item if not greater than anything in the items array it simply gets pushed back. We use an itemAdded boolean flag to help us know whether the new queue item was added or not. If it wasn’t we use a simple push method to push it onto the array. Our print method also just iterates over the items array and logs each objects name and priority. Please note, i left out the other helper methods, like front, back, empty, etc. Nothing has changed for them, so i left it out so the code is shorter to read. However if you download the source on github, you will find the complete code with comments.

Thats pretty much it for queues! I hope this gives you a basic idea of how javascript queues work and how to implement them. You can apply these principles in your own language (though some method implements might be slightly different). I will provide more sample code in my git repository so you can see more use cases for using javascript queues in your own projects. Feel free to reach out on twitter as well ( @scriptonian ) if you have any questions. Thanks for reading!