In this segment, we will provide an overview of the queue data structure and explore the implementation of a queue using JavaScript.
What is Queue?
A queue is a specific type of data structure that organizes information in a sequential manner, much like a line of individuals waiting to cast their votes. In this analogy, the person at the front of the line will be the first to vote and subsequently exit the queue. This behavior mirrors that of a data queue, where the element positioned at the front is the first to be removed, and this process continues accordingly. Consequently, the queue operates under the FIFO (first-in, first-out) principle, indicating that the element that enters the queue first will be the one to exit first. Therefore, the queue data structure serves as an ordered collection of data values, with new values being added at the rear and existing values being extracted from the front.
Implementing a Queue
Let us examine an illustration that will help us grasp the concept of queue implementation:
class Queue1 {
constructor (){
this.data = [];
this.rear = 0;
this.size = 10;
}
}
In the above code, we have used the following three variables where each variable specifies their use as:
- data: It is the array where we store the values or elements of the queue.
- rear: It is the variable that is used for storing the position value where the next element will get inserted in the queue.
- size: It is the size defined for the queue that will tell the number of elements contained in a queue.
In a manner akin to stack operations, a queue also comprises two primary functions that allow us to add an element to the queue or extract an existing one. These functions are as follows:
- Enqueue: The enqueue function is utilized to add an element to the queue. This action appends an element at the rear end of the queue.
- Dequeue: The dequeue function is employed when we wish to eliminate or take out an existing element from the queue. This operation facilitates the removal of an element from the front end of the queue.
In respect to these main methods of the queue, there are some other methods also available that can be applied over the queue, which are:
- Peek : The peek method is used to get the value that is present at the front end of the queue.
- isEmpty : Such an operation is used to check if the queue has elements or it is empty.
- printQueue : The printQueue function is used to return all the elements present in the queue in the form of a string.
We will explore the hands-on execution of these queue operations.
Implementing Queue Operations
At this point, we will explore the hands-on execution of these queue operations, which include the following:
1) enqueue : This is the operation associated with a queue that facilitates the addition of elements into the queue.
Example:
enqueue(ele) {
if(this.rear < this.size ) {
this.data[this.rear] = ele;
this.rear = this.rear + 1;
}
}}
In the code provided above, elements have been inserted into the queue utilizing the push function.
2) dequeue : This is the queue operation employed to remove or extract existing values from the queue.
Example:
dequeue() {
if(this.isEmpty() === false) {
this.rear = this.rear-1;
return this.data.shift();
}
}
In the code provided above, the initial step involves verifying whether the queue is empty. This is important because an empty queue will lead to an "Underflow" condition. If the queue is not empty, it proceeds to examine and return the element present in the queue.
3) Length : The queue function retrieves and returns the total number of elements currently present in the queue.
Example:
length() {
return this.rear;
}
The expression this.rear will assist in retrieving the current length of the queue.
4) isEmpty : This function serves to determine if the queue is devoid of elements. When the queue is identified as empty, it will return true. Conversely, if there are elements present, it will return false.
Example:
isEmpty() {
return this.rear === 0;
}
In the provided code, it evaluates whether the value of the rear, which represents the end, is equal to 0. If this condition is satisfied, it will return true; otherwise, it will return false.
5) print : This operation for the queue is utilized to display the elements contained within the queue, starting from the index value 0 and extending to the rear position of the queue.
Example:
print() {
for(let i =0; i < this.rear; i++) {
console.log(this.data[i]);
}
}
In the code provided, a for loop is utilized that starts from the 0 index and iterates up to the rear position of the queue. During this process, it will display the value and simultaneously store it in the data array.
6) clear : This queue operation serves to remove or eliminate all elements present in the queue, subsequently resetting the value of the rear to 0.
Example:
clear() {
this.data.length = 0;
this.rear = 0;
}
In the code presented above, the invocation of the clear method results in the data array being reset to 0, and the rear variable is also assigned a value of 0.
Implementing the JavaScript Queue
The complete code:
class Queue {
constructor(){
this.data = [];
this.rear = 0;
this.size = 20;
}
enqueue(ele) {
if(this.rear < this.size ) {
this.data[this.rear] = ele;
this.rear = this.rear + 1;
}
}
length() {
return this.rear;
}
isEmpty() {
return this.rear === 0;
}
getFront() {
if(this.isEmpty() === false) {
return this.data[0];
}
}
getLast() {
if(this.isEmpty() === false) {
return this.data[ this.rear - 1 ] ;
}
}
dequeue() {
if(this.isEmpty() === false) {
thisthis.rear = this.rear-1;
return this.data.shift();
}
}
print() {
for(let i =0; i < this.rear; i++) {
console.log(this.data[i]);
}
}
clear() {
this.data.length = 0;
this.rear = 0;
}
}
While the operational characteristics of a queue remain consistent across all programming languages, the implementation and syntax differ depending on the specific programming language being utilized.