Introduction
A queue is a data structure widely used in computers, applications, etc. A queue in programming works exactly like a queue in real life. In this article, you will learn what a queue is and how to implement a queue in JavaScript.
What is a Queue?
A Queue is First In First Out
As mentioned above, A queue in programming functions is just like a queue in the real world. Drive-thru is a great example of a queue. Please take a look at the picture below.
This is a graph of a drive-thru. As you can see, the first car entering the drive-thru leaves first. A car right behind car 1 can only leave after car 1 is gone. In addition, a car 8 that just enters the drive-thru needs to wait for the seven cars in front to exit. This behavior of a queue is called First In First Out (FIFO). The same logic is applied to a queue in programming. The only difference is that, in programming, things that are in a queue are data such as numbers, strings, and JavaScript objects and not actual cars.
A Queue is an Abstract Data Structure
An Abstract Data Structure is a concept that is a set of data and operations for manipulating the data. The key point is that how it is implemented is not a part of it as that varies depending on (1) what language you use and (2) how you implement it in the same language.
For instance, if you use C language, a queue is created with “Structure”. However, if you choose object-oriented languages such as JavaScript and Python, you use “Class”.
Let’s assume that you use JavaScript. It can be implemented by using Array, Forward Linked List, or Doubly Linked List. You can choose among them and implementation is different from each other. (In this article, I will cover Forward Linked List. If you want to know the implementations of the others, You can go visit My repository on Github)
Implementation with Forward Linked List
What is Forward Linked List?
Forward Linked List (in short FLL) is a list of elements in which each element possesses a value and a pointer to the next element. A graph below describes FLL.
Elements are denoted as red boxes and pointers are represented as black arrows.
The first element of FLL has 6 and a pointer to the next element which is an element with a value of 8. Do you notice that a head points at the first element? That is to make sure that the element of the value of 6 is the first element. In the same way, the tail points to an element at the end of a queue. The last pointer points at null. This indicates that it is the element that holds the pointer is the last element of a list.
Methods for a Queue
There are in total four methods for a queue: _isEmpty, dequeue, enqueue and display method.
_isEmpty
This method checks whether a queue has an element or elements. If it has, it returns false. Otherwise, it returns true. The main purpose of this code is not to write the same codes over and over. This method is used only by the other methods. The underscore at the beginning of the method name is to distinguish between this method and the others. A method invoked only inside of a class is called a private method. (Adding underscore to a private method is one of JavaScript Naming Conventions. If you want to know about it more, go to this link.)
dequeue
A method dequeue is a function for removing an element from a queue.
enqueue
A method enqueue is a function for inserting an element into a queue.
display
This method displays a current state of a queue in a console.
Time and Space Complexity
Two functions: en-queue and de-queue take only O(1) time complexity as it changes the head and the end of a queue. However, creating a queue with n elements takes O(n).
Implementation
// Forward Linked List Queue
class Element {
constructor(val) {
this.val = val;
this.next = null;
}
}
class FLLqueue {
constructor() {
this.head = null;
this.tail = null;
}
_isEmpty() {
return !!(this.head === null && this.tail === null);
}
enqueue(e) {
if (this._isEmpty()) {
this.head = e;
} else {
this.tail.next = e;
}
this.tail = e;
}
dequeue() {
if (this._isEmpty()) {
return null;
}
const result = this.head;
if (this.head.next) {
this.head = this.head.next;
} else {
this.tail = null;
this.head = null;
}
return result;
}
display = () => {
if (this._isEmpty()) {
return "There is no element!";
}
let result = "Exit[ ";
let current = this.head;
while (true) {
if (current === null) {
result += "] Entrance";
break;
}
result += current.val + " ";
current = current.next;
}
return result;
};
}
// ----------------------------------------------
const e1 = new Element(1);
const e2 = new Element(2);
const e3 = new Element(3);
const e4 = new Element(4);
const e5 = new Element(5);
const queue = new FLLqueue();
queue.enqueue(e1);
console.log(queue.display());
// Exit[ 1 ] Entrance
queue.dequeue();
console.log(queue.display());
// There is no element!
queue.enqueue(e2);
queue.enqueue(e3);
queue.enqueue(e4);
queue.enqueue(e5);
console.log(queue.display());
// Exit[ 2 3 4 5 ] Entrance
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
// making sure that is works properly when there is no element in a queue.
queue.dequeue();
console.log(queue.display());
// There is no element!Explained in Detail
We have two classes. A class Element is for an element and FLLQueue is for a queue. Therefore, instances of a class Element are in a queue. FLL Queue has a head and a tail which are initialized as null.
enqueue
it first checks whether a queue is empty. If it is empty, it set a head pointer to a new element. If a queue already has an element or elements, a pointer of the current tail changes null to a new element. Then, set the tail pointer points to a new element.
dequeue
it first checks whether a queue is empty. If it is empty, it simply returns null because it cannot remove an element. If it is not empty, it first stores a removing element to a result. Then it checks if that element is not the only element in a queue. If it is not the only element, it simply set the head to the next element. If it is the only element, it is required to make a head pointer set to a null just like it does to a tail in order to create an empty queue.
display
To iterate a queue, it uses a while-loop to go through from the head to the tail.
Conclusion
A queue is a basic data structure and it is necessary to understand how it works because many data structures such as HashTable use this structure. I hope this article helps you understand better about a queue.