How to Queue in JavaScript?

Last updated: November 11th, 2020

In computer science, data structures define the way data is stored and organised, this allows computers to perform operations more efficiently.

A queue is a data structure, that models real-world queues that allow insertion and removal of data. Just like a ticket line, the back of the queue allows a person to insert themselves into the queue (enQueue) and a person can only be removed from the front (deQueue). Queues are open at both ends and follow a FIFO (First In First Out) data structure, meaning the first person in the queue will be seen first — preventing arguments in the ticket line!

Queue Implementation

The queue data structure has two main methods: a method to add (enQueue) items and to remove (deQueue) items from the queue. We will also add other methods including storageLength, isEmpty, isFull, and peek.

The first step is to create a Queue class with a maxSize parameter and storage property:

class Queue {
    constructor(maxSize) {
        this.maxSize = maxSize
        this.storage = {}
    }
}

The constructor() method allows us to accept maxSize as an argument, which is the limit of items that can be stored in the queue. So every time a new Queue() is created, the constructor method creates a new object, that by default will have the maxSize value and an empty object to store the queue items.

To keep a track of the queue items, we will add a frontIndex and backIndex property to our Queue class set to 0 and -1 respectively.

class Queue {
  constructor(maxSize) {
          this.maxSize = maxSize,
      this.storage = {},
      this.frontIndex = 0,
      this.backIndex = -1;
  }
}

Queue Methods:

The first method we will add is storageLength, which calculates the length of the queue at a particular time point.

storageLength() { 
    return this.backIndex - this.frontIndex + 1;
  }

We can understand this better with an example:

If we add 3 items to the queue, the backIndex will increase by 3 to reflect the addition of the items to the queue. The backIndex value is now 2, which you visualise as an array of 3 items ⇒ [0, 1, 2]Therefore the storageLength is 2 - 0 + 1 = 3

The next method is theenQueue method that allows us to add new items to the queue, only if thestorage is not exceeding the maxSize.

enQueue(item) {
    if (this.storageLength() < this.maxSize) {
      this.storage[++this.backIndex] = item;
    }
  }

The backIndex is increased by 1 and the new item is placed in the last index of the queue storage. The backIndex is now 0 meaning the last item that was placed is actually in the first position - which makes sense because we have only added one item so far!

The deQueue method is used to remove items from the front of the queue, only if the queue storage has items to remove.

deQueue() {
    if (this.storageLength() !== 0) {
      delete this.storage[this.frontIndex++];
    }
  }

In the removal of items from the queue, the frontIndex is important as a queue operates on FIFO (First In First Out). The item was in the first position so the frontIndex will be increased by 1 to reflect that the first item in the queue is now as index 1.

We can also check if a queue isFull or isEmpty by using the storageLength method to verify the condition of the queue storage.

isEmpty() {
    return !this.storageLength();
  }
isFull() {
    return this.storageLength() === this.maxSize ? true : false;
  }

Lastly, the peek method can be used to return the item at the front of the queue without removal.

peek() {
   return this.storage[this.frontIndex];
  }