Hey programmers, today we will look at Queue data structure and we will implement it in JavaScript. This article is divided into five different parts.
So, let's get started...
Introduction
The queue is a linear data structure that works on the principle of first in first out (FIFO). FIFO means elements that are inserted first will be removed first. A real-world example of the queue is the customer queue where the customer who came first served first.
So, the queue has a front and a rear end, the elements in the queue are inserted from the rear end and removed from the front end. Image source - javatpoint.com
Operations
Primarily, there are four basic operations we can perform on a queue.
- Enqueue - Adding an element to the end of the queue
- Dequeue - Removing the element from the beginning of the queue
- isEmpty - Checking if the queue is empty
- peek - get the first element in the queue without removing it
Implementation
We will implement this in JavaScript using the class syntax and array methods. Let's first make our constructor function which will initialize the queue.
class Queue {
constructor() {
this.items = [];
}
}
Now, we will add the different methods to work with this queue. Let's add an enqueue method to add the element at the end of the queue. We will use the array push() method to add the element at the end.
class Queue {
// constructor()
enqueue(item) {
this.items.push(item);
}
}
To add the dequeue method which removes the item from the start of the array, we will use the array shift() method which removes the item from the start of the array and returns it.
class Queue {
// constructor()
// enqueue(item)
dequeue() {
return this.items.shift();
}
}
To check if the queue is empty we will use the length property of the array and comparison operator to compare it with value 0
class Queue {
// constructor()
// enqueue(item)
// dequeue()
isEmpty() {
return this.items.length == 0;
}
}
Now, for the peek() method we will use the bracket notation to access the first element in the queue without removing it.
class Queue {
// constructor()
// enqueue(item)
// dequeue()
// isEmpty()
peek() {
return this.items[0];
}
That's how we can implement a queue. Let's look at the whole code once again.
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item);
}
dequeue() {
return this.items.shift();
}
isEmpty() {
return this.items.length == 0;
}
peek() {
return this.items[0];
}
}
Working With Queue
So we implemented all the required methods that define a queue. In the code example below, we will look at if they are performing as we want them to.
// Initialize the queue using the new keyword
const queue = new Queue();
// first we will check if the queue is empty
queue.isEmpty(); // true
// let's add some elements to the queue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// now, check if it is empty
queue.isEmpty(); // false
// remove the first element from the queue
queue.dequeue(); // 1
// now, we want to check what the first element is
queue.peek(); // 2
// remove the remaining elements
queue.dequeue(); // 2
queue.dequeue(); // 3
// again check if we have removed all the elements
queue.isEmpty() // true
Applications of Queue
- Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
- Queues are used in the asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
- Queues are used as buffers in most applications like MP3 media player, CD player, etc.
- Queues are used to maintain the playlist in media players in order to add and remove the songs from the playlist.
- Queues are used in operating systems for handling interrupts.
Source: javatpoint.com
If you liked this article, you will love my tweets. I share useful tips and resources that may help you learn Web Development & grow as a developer.
You can follow me on
Thank you for reading this. I will see you in the next post. Till then, keep coding :)