Queue implementation in JavaScript

Saturday, Jan 18, 2020
JavaScript DataStructures

Queue is like a vector in that the elements are sequentially ordered but with some key differences:

only the head element (first one) is accessible as in FIFO (first in first out)
size is extensible (can add and remove elements from the queue)

A queue can be used in situation when there are multiple objects that need to use a single resource. The resource can process only one object at a time so the other objects must wait. For example, in distributed computing, we can send multiple jobs to the processor where these jobs must wait until the processor is available.

Queue Operations

new Queue()        // create a new queue
HEAD(q)            // return the first element
ENQUEUE(obj, q)    // add object to q's tail
DEQUEUE(q)         // remove and return object from the head
EMPTY(q)           // check if queue is empty

I again used JavaScript's constructor to create a queue:

JavaScript Implementation

// Implementing a queue
//
// create a constructor for queue
function Queue() {
    this.data = [];
    this.isEmpty = true;
    this.head = null;
}

// enqueue method for queue adds `value` to the tail
Queue.prototype.enqueue = function(value)
{
    if (this.isEmpty)
    {
        this.data[0] = value;
        this.head = this.data[0];
        this.isEmpty = false;
    }
    else
    {
        this.data[this.data.length] = value;
    }
};

// dequeue method for queue
// return head element
Queue.prototype.dequeue = function()
{
    if (this.isEmpty)
        console.log("Queue is already empty!");
    else
    {
        head = this.data[0];
        for (var i = 0; i < this.data.length - 1; i++)
            this.data[i] = this.data[i + 1];
        this.data.pop();
        this.head = this.data[0];
        if (this.data.length == 0)
        {
            this.head = null;
            this.isEmpty = true;
        }
        return head;
    }
};

Let's test it

q = new Queue();
console.log(q.head);
console.log(q.isEmpty);

//add three elements to tail
q.enqueue(5);
q.enqueue(6);
q.enqueue(87);

console.log(); console.log("Head is", q.head);
console.log("Is q empty?", q.isEmpty);

// remove two elements from head
q.dequeue();
q.dequeue();

console.log();
console.log("Head is", q.head);
console.log("Is q empty?", q.isEmpty);

q.dequeue();

console.log();
console.log("Head is", q.head);
console.log("Is q empty?", q.isEmpty);

q.dequeue(); // try removing element from an empty queue

null
true

Head is 5
Is q empty? false

Head is 87
Is q empty? false

Head is null
Is q empty? true
Queue is already empty!