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?).
The Queue Class
Lets write a basic queue class
Simple! We create a class with one property: items, which will be used to store our collection items. Lets create the ES2015 version
Now we will implement the queue helper classes.
and here is the ES2015 version
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
And the ES2015 version
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.
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
And the ES2015 version
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
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.