We have already learned how stacks work. Queues are very similar, but instead of LIFO, they use a different principle that you will learn about in this chapter.
A queue is an ordered collection of items that follows the FIFO (which stands for First In First Out, also known as first-come first-served) principle. The addition of new elements in a queue is at the tail and the removal is from the front. The newest element added to the queue must wait at the end of the queue.
The most popular example of a queue in real life is the typical line that we form from time to time:
We have lines for movies, the cafeteria, and a checkout line at a grocery store, among other examples. The first person that is in the line is the first one that will be attended.
A very popular example in Computer Science is the printing line. Let's say we need to print five documents. We open each document and click on the print button. Each document will be sent to the print line. The first document that we asked to be printed is going to be printed first and so on, until all documents are printed.
We are going to create our own class to represent a queue. Let's start from the basics and declare our class:
function Queue() {
//properties and methods go here
}First, we need a data structure that will store the elements of the queue. We can use an array to do it, just like we used for the Stack class in the previous chapter (you will notice the Queue and Stack class are very similar, just the principles for adding and removing the elements are different):
var items = [];
Next, we need to declare the methods available for a queue:
enqueue(element(s)): This adds a new item (or several items) at the back of the queue.dequeue(): This removes the first item from the queue (the item that is in the front of the queue). It also returns the removed element.front(): This returns the first element from the queue, the first one added, and the first one that will be removed from the queue. The queue is not modified (it does not remove the element; it only returns the element for information purposes—very similar to thepeekmethod from theStackclass).isEmpty(): This returnstrueif the queue does not contain any elements andfalseif the queue is bigger than 0.size(): This returns how many elements the queue contains. It is similar to thelengthproperty of the array.
The first method we will implement is the enqueue method. This method will be responsible for adding new elements to the queue with one very important detail; we can only add new items to the end of the queue:
this.enqueue = function(element){
items.push(element);
};As we are using an array to store the elements for the stack, we can use the push method from the JavaScript array class that we covered in Chapter 2, Arrays, and also in Chapter 3, Stacks.
Next, we are going to implement the dequeue method. This method will be responsible for removing the items from the queue. As the queue uses the FIFO principle, the first item that we added is the one that is removed. For this reason, we can use the shift method from the JavaScript array class that we also covered in Chapter 2, Arrays. If you do not remember, the shift method will remove the element that is stored at the index 0 (first position) of the array:
this.dequeue = function(){
return items.shift();
};With the enqueue and dequeue methods being the only methods available for adding and removing items from the queue, we assured the FIFO principle for our own Queue class.
Now, let's implement some additional helper methods for our class. If we want to know what the front item of our queue is, we can use the front method. This method will return the item from the front of the queue (index 0 of the array):
this.front = function(){
return items[0];
};The next method is the isEmpty method, which returns true if the queue is empty and false otherwise (note that this method is the same as the one in the Stack class):
this.isEmpty = function(){
return items.length == 0;
};For the isEmpty method, we can simply verify that the length of the internal array is 0.
Like the length property of the array class, we can also implement the same for our Queue class. The size method is also the same for the Stack class:
this.size = function(){
return items.length;
};And we are done! Our Queue class is implemented. Just like we did for the Stack class, we can also add the print method:
this.print = function(){
console.log(items.toString());
};And now we are really done!
Let's take a look how our Queue class looks like after its full implementation:
function Queue() {
var items = [];
this.enqueue = function(element){
items.push(element);
};
this.dequeue = function(){
return items.shift();
};
this.front = function(){
return items[0];
};
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}The first thing we need to do is instantiate the Queue class we just created. Next, we can verify that it is empty (the output is true because we have not added any elements to our queue yet):
var queue = new Queue(); console.log(queue.isEmpty()); //outputs true
Next, let's add some elements to it (let's enqueue the elements "John" and "Jack"—you can add any element type to the queue):
queue.enqueue("John");
queue.enqueue("Jack");Let's add another element:
queue.enqueue("Camila");Let's also execute some other commands:
queue.print(); console.log(queue.size()); //outputs 3 console.log(queue.isEmpty()); //outputs false queue.dequeue(); queue.dequeue(); queue.print();
If we ask to print the contents of the queue, we will get John, Jack, and Camila. The size of the queue will be 3 because we have three elements queued on it (and it is also not going to be empty).
The following diagram exemplifies all the enqueue operations we executed so far and the current status of our queue:
Next, we asked to dequeue two elements (the dequeue method is executed twice). The following diagram exemplifies the dequeue method execution:
And when we finally ask to print the content of the queue again, we only have the element Camila. The first two elements queued, were dequeued; the final element queued to the data structure is the last one that will be dequeued from it. That being said, we are following the FIFO principle.