First Things First...
Before we get our hands dirty working on building a queue in Javascript we should first understand what a queue is. A queue like a linked list is a linear data structure. This means that all the elements of a queue are placed sequentially. Unlike a stack a queue doesn't have a rounded bottom. Instead, operations can be performed on both sides of a queue.
Queues follow a FIFO operation order, meaning what goes in first comes out first. An easy way to picture this is to imagine a line of people waiting to buy items from a supermarket.
People enter at the back and the first person to enter the line is the first to leave it. Now let us look at how we can implement a queue using Javascript.
Right into the Code
Now that you have a basic understanding of what queues are let us implement it. There are two ways to implement queues in Javascript:
- Using Arrays and Built in Functions
- Using Classes
The basic operations on queues are dequeue and enqueue, but we will also be looking at isEmpty and peek
Implementing a Queue Using Arrays and Built in Functions
A basic understanding of arrays is all you need to implement queues using this method. The concept is to first initialize and array, then use built in functions to create a queue.
let queue = [4,3,2,1];
Now that we have an array we can use built in functions to make this array act as a queue.
queue.push(0);
console.log(queue);
queue.push(-1);
console.log(queue);
queue.shift();
console.log(queue);
The code above would return the following:
[ 4, 3, 2, 1, 0 ]
[ 4, 3, 2, 1, 0, -1 ]
[ 3, 2, 1, 0, -1 ]
The Array.Push() and Array.Shift() functions act as the enqueue and dequeue operations respectively. New elements can only be added at the back and elements are removed only from the front.
We can simply implement the peek operation by returning the first element in line after checking if the queue has elements in it.
if(queue.length){
return queue[0];
}else{
return null;
}
We can do something similar for the isEmpty operation and return true when the queue is empty and return false when it isn't.
if(!queue.length){
return true;
}else{
return false;
}
That was easy, now let us look at how we can implement a queue using Javascript classes.
Implementing a Queue Using Classes
The concept here isn't much different from the implementation of queue using arrays and built in functions. To start things of we first need to create a queue class, then every time we need a queue all we need to do is instantiate an object of that class.
class Queue{
constructor(){
this.queue = [];
}
}
The constructor will be creating an array every time an object is instantiated.
class Queue{
constructor(){
this.queue = [];
}
enqueue(elem){
this.queue.push(elem);
}
}
The enqueue function now pushes whatever is passed into it into the "queue" array that is created whenever a new queue object is created.
class Queue{
constructor(){
this.queue = [];
}
enqueue(elem){
this.queue.push(elem);
}
dequeue(){
if(this.queue.length){
return this.queue.shift();
}else{
return null;
}
}
}
The dequeue function removes the first element from the queue and returns the value of the element after checking if the queue has elements in it. If the queue is empty it returns "null".
class Queue{
constructor(){
this.queue = [];
}
enqueue(elem){
this.queue.push(elem);
}
dequeue(){
if(this.queue.length){
return this.queue.shift();
}else{
return null;
}
}
isEmpty(){
return this.queue.length === 0;
}
}
The isEmpty function returns a Boolean value that's based on the value of the queue's length. If the queue has no elements, a length of 0, it returns "true". If the queue length is not zero it returns "false".
class Queue{
constructor(){
this.queue = [];
}
enqueue(elem){
this.queue.push(elem);
}
dequeue(){
if(this.queue.length){
return this.queue.shift();
}else{
return null;
}
}
isEmpty(){
return this.queue.length === 0;
}
peek(){
if(!this.isEmpty()){
return this.queue[0];
}
return null;
}
}
Finally the "peek" function above returns the value of the element at the front of the queue after checking if the queue is empty or not.
Done! Now let us instantiate an object and perform the operations on it.
let queue = new Queue;
queue.isEmpty();
queue.enqueue(4);
queue.enqueue(3);
queue.enqueue(2);
queue.enqueue(1);
queue.peek();
queue.isEmpty();
queue.dequeue();
queue.dequeue();
queue.peek();
Well Done! Now you know how to implement a queue using Javascript arrays and classes.
