JavaScript Queue Implementation

In this article, we are going to create our own class to represent a Queue in JavaScript.

The Queue Data Structure Overview

What is a Queue?

A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at another end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.
A queue is a data structure used for storing data (similar to Linked Lists and Stacks). In a queue, the order in which data arrives is important. In general, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence.

Real World Examples

A real-world example of a queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Queue Concepts

  • When an element is inserted in a queue, the concept is called EnQueue.
  • When an element is removed from the queue, the concept is called DeQueue.
  • dequeuing an empty queue is called underflow (treat as Exception).
  • EnQueuing an element in a full queue is called overflow (treat as Exception).

Queue Implementation Overview

We are now going to create our own class to represent a queue. First, we need a data structure that will store the elements of the queue. We can use an array to do it:
let items = [];
Next, we need to declare the methods available for a queue:
  • enqueue(element(s)): This adds a new item (or several items) at the back of the queue.
  • dequeue(): This removes the first item from the queue (the item that is in the front of the queue). It also returns the removed element.
  • front(): This returns the first element from the queue, the first one added, and the first one that will be removed from the queue.
  • isEmpty(): This returns true if the queue does not contain any elements, and false if the queue is bigger than 0.
  • size(): This returns the number of elements the queue contains. It is similar to the length property of the array.

Enqueue elements to the queue

The enqueue(element(s)) method: This adds a new item (or several items) at the back of the queue.
 enqueue(element) {
        this.items[this.count] = element;
        this.count++;
 }

Dequeue elements from the queue

The dequeue() method: This removes the first item from the queue (the item that is in the front of the queue). It also returns the removed element.
 dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
  }

Peeking the element from the front of the queue

peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
 }

Verifying if the queue is empty

The isEmpty() Method: This returns true if the queue does not contain any elements, and false if the queue is bigger than 0.

isEmpty() {
        return this.size() === 0;
}

Queue Implementation in JavaScript

// @ts-check

class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }

    enqueue(element) {
        this.items[this.count] = element;
        this.count++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }

    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }

    isEmpty() {
        return this.size() === 0;
    }

    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }

    size() {
        return this.count - this.lowestCount;
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

Using Queue

const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('Ramesh');
queue.enqueue('Tony');
console.log(queue.toString()); // Ramesh,Tony
queue.enqueue('Cuise');
console.log(queue.toString()); // Ramesh,Tony,Cuise
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove Ramesh
queue.dequeue(); // remove Tony
console.log(queue.toString()); // Cuise

Output

true
Ramesh,Tony
Ramesh,Tony,Cuise
3
false
Cuise

Comments

Post a Comment