Implementation of Queue in Javascript

Last Updated : 20 Dec, 2023

In This article, we will be implementing Queue data structure in JavaScript. A Queue works on the FIFO(First in First Out) principle. Hence, it performs two basic operations which are the addition of elements at the end of the queue and the removal of elements from the front of the queue. Like Stack, Queue is also a linear data structure.

Note: Assuming a queue can grow dynamically we are not considering the overflow condition Now let’s see an example of a queue class using an array:-

To implement a queue data structure we need the following methods:

enqueue : To add elements at the end of the queue.
dequeue: To remove an element from the front of the queue.
peek: To get the front element without removing it.
isEmpty: To check whether an element is present in the queue or not.
printQueue: To print the elements present in the queue.

First, we will be implementing the data structure by creating a queue object and defining the methods for it. We will use additional variables and time complexity will be O(1) which will make the execution of functions faster irrespective of the size of the queue. The additional variables keep track of the index of the first and last element so we do not have to iterate the queue at each insertion and deletion.

Implementation:

Javascript

class Queue {
    constructor() {
        this.items = {}
        this.frontIndex = 0
        this.backIndex = 0
    }
    enqueue(item) {
        this.items[this.backIndex] = item
        this.backIndex++
        return item + ' inserted'
    }
    dequeue() {
        const item = this.items[this.frontIndex]
        delete this.items[this.frontIndex]
        this.frontIndex++
        return item
    }
    peek() {
        return this.items[this.frontIndex]
    }
    get printQueue() {
        return this.items;
    }
}
const queue = new Queue()
console.log(queue.enqueue(7))
console.log(queue.enqueue(2))
console.log(queue.enqueue(6))
console.log(queue.enqueue(4))
console.log(queue.dequeue())
console.log(queue.peek())
let str = queue.printQueue;
console.log(str)

Output:

Explanation: The insertion and deletion of items are performed in O(1) because of variables frontIndex and backIndex.

Time complexity:

Enqueuing an element: O(1)
Dequeuing an element: O(n) (as all the remaining elements need to be shifted one position to the left)
Accessing the front of the queue: O(1)

Space complexity:

O(n), where n is the number of elements in the queue.

We can also create a queue using array and use the inbuilt array methods to implement the queue functions. The only drawback of inbuilt array methods is that they perform operations in O(n) time complexity.

Example: Showing class Queue and it’s constructor.

Javascript

// Queue class
class Queue{
    // Array is used to implement a Queue
    constructor() {
        this.items = [];
    }
                 
    // Functions to be implemented
    // enqueue(item)
    // dequeue()
    // peek()
    // isEmpty()
    // printQueue()
}

As in the above definition we have created a skeleton of a queue class which contains a constructor in which we declare an array to implement queue. Hence, with the creation of an object of a queue class this constructor would be called automatically and the array will be declared Let’s implement each of these functions:

Example: JavaScript enqueue() adds an element to the queue.

Javascript

// enqueue function
enqueue(element){    
    // adding element to the queue
    this.items.push(element);
}

This function adds an element at the rear of a queue. We have used push() method of array to add an element at the end of the queue.

Example: JavaScript dequeue() removes an element from the queue.

Javascript

// dequeue function
dequeue()
{
    // removing element from the queue
    // returns underflow when called
    // on empty queue
    if(this.isEmpty())
        return "Underflow";
    return this.items.shift();
}

This function removes an element from the front of a queue . We have used shift method of an array to remove an element from the queue.

Example: JavaScript peek() returns the front/top element of the queue.

Javascript

// peek function
peek()
{
    // returns the Front element of
    // the queue without removing it.
    if(this.isEmpty())
        return "No elements in Queue";
    return this.items[0];
}

This function returns the front element of the queue. We simply return the 0th element of an array to get the front of a queue.

In this function we have used the length property of an array and if the array length is 0 then the queue is empty.

Helper Methods

Let’s declare some helper method which is quite useful while working with the queue.

Example: JavaScript isEmpty() returns true if the queue is empty

Javascript

// isEmpty function
isEmpty() {
    // return true if the queue is empty.
    return this.items.length == 0;
}

Example: JavaScript printQueue() returns all the elements of a queue.

Javascript

// printQueue function
printQueue()
{
    let str = "";
    for(var i = 0; i < this.items.length; i++)
        str += this.items[i] +" ";
    return str;
}

In this method, we concatenate all the elements of the queue in a string and return the string

Note: Different helper methods can be declared in the Queue class as per the requirement.

Implementation

Now let’s use the queue class and its different method described above

Javascript

// creating object for queue class
let queue = new Queue();
          
// Testing dequeue and pop on an empty queue
// returns Underflow
console.log(queue.dequeue());
 
// returns true
console.log(queue.isEmpty());
 
// Adding elements to the queue
// queue contains [10, 20, 30, 40, 50]
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60);
 
// returns 10
console.log(queue.peek());
 
// removes 10 from the queue
// queue contains [20, 30, 40, 50, 60]
console.log(queue.dequeue());
 
// returns 20
console.log(queue.peek());
 
// removes 20
// queue contains [30, 40, 50, 60]
console.log(queue.dequeue());
 
// printing the elements of the queue
// prints [30, 40, 50, 60]
console.log(queue.printQueue());

Output:

Underflow
true
10
20
[30, 40, 50, 60]

Now once we are done with the implementation of the Queue class we can use it in different applications.

Application: An Interesting Method to Generate Binary Numbers from 1 to n

In this problem, we generate different binary numbers from 1 to n.

Javascript

// function to generate binary numbers
function generatePrintBinary(n)
{
    // Create an empty queue of strings
    let q = new Queue();
         
    // Enqueue the first binary number
    q.enqueue("1");
         
    // This loops is like BFS of a tree with 1 as root
    // 0 as left child and 1 as right child and so on
    while(n-- > 0)
    {
        // print the front of queue
        let s1 = q.front();
        q.dequeue();
        console.log(s1);
             
        // Store s1 before changing it
        let s2 = s1;
             
        // Append "0" to s1 and enqueue it
        q.enqueue(s1 + "0");
             
        // Append "1" to s2 and enqueue it. Note that s2 contains
        // the previous front
        q.enqueue(s2 + "1");
    }
}
 
// calling the above function    
// prints [1 10 11 100 101]
generatePrintBinary(5);

Output:

GeeksforGeeks

Improve

Previous Article

JavaScript program to implement stack using queue

JavaScript Program for Implementation of Queue using Linked List

Similar Reads

Should we declare as Queue or Priority Queue while using Priority Queue in Java?

Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

What is the difference between Microtask Queue and Callback Queue in asynchronous JavaScript ?

To know the difference between Microtask Queue and Callback Queue, we need to have a clear idea of how does asynchronous JavaScript gets executed and what are the roles that Microtask Queue and Callback Queue play. Functions or operations running parallel with the other functions or operations are called asynchronous functions or operations in Java

Implementation of Priority Queue in Javascript

Priority Queue is an extension of Queue having some properties as follows: Each element of the priority queue has a priority associated with it.Elements are added to the queue as per priority.Lowest priority elements are removed first.We can design a priority queue using two approaches in the first case we can add the queue element at the end of th

JavaScript Program for Implementation of Queue using Linked List

A queue is a linear data structure that follows the First In, First Out, FIFO principle, where elements are added at the rear and removed from the front. We must implement a queue data structure using a linked list and provide operations such as enqueue, dequeue, peek, and isEmpty. Linked list-based queues offer constant-time enqueue, dequeue, peek

What is Priority Queue | Introduction to Priority Queue

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values. In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its

Stack and Queue in Python using queue Module

A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.

Check if a queue can be sorted into another queue using a stack

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp

Reversing a Queue using another Queue

Given a queue. The task is to reverse the queue using another empty queue. Examples: Input: queue[] = {1, 2, 3, 4, 5} Output: 5 4 3 2 1 Input: queue[] = {10, 20, 30, 40} Output: 40 30 20 10 Approach: Given a queue and an empty queue.The last element of the queue should be the first element of the new queue.To get the last element there is a need to

Advantages of circular queue over linear queue

Linear Queue: A Linear Queue is generally referred to as Queue. It is a linear data structure that follows the FIFO (First In First Out) order. A real-life example of a queue is any queue of customers waiting to buy a product from a shop where the customer that came first is served first. In Queue all deletions (dequeue) are made at the front and a

Difference between Queue and Deque (Queue vs. Deque)

Queue: The queue is an abstract data type or linear data structure from which elements can be inserted at the rear(back) of the queue and elements can be deleted from the front(head) of the queue. The operations allowed in the queue are:insert an element at the reardelete element from the frontget the last elementget the first elementcheck the size

Article Tags :

Practice Tags :

Queue