Forgot Your Password?

Choose Your Plan

Start Building Real Apps

Pay Monthly

12

Pay Yearly

10
2 months free
Top shelf web developer training.

Guided Paths

Follow our crafted routes to reach your goals.

Courses

Premium content to build real apps.

Code Tutorials

Examples to follow and learn from.

Data Structure in Web - Queues

What is a Queue?

Queue is a programming construct which bears heavy resemblance with the real world queues for example a queue at the movie theater, ATMs or the bank.

A more computer sciency definition of queue would be

An abstract data collection in which the elements can be added to the back called enqueue and removed form the front called dequeue which makes it a FIFO data structure

Ofcourse having only enqueue and dequeue operations are not going to be enough for our Queue, so we are going make it similar to the Queue in Java.

Types

Before we jump in and implement a queue, let us take a look at the different types of queues:

  1. Simple Queue - The queue discussed above

  2. Circular Queue - Similar to simple queue except the back of the queue is followed by the front of the queue

  3. Priority Queue - Contains elements with a predefined priority

  4. Dequeue (Double Ended queue) - Similar to Simple Queue but can add or remove elements for either the front or the back of the queue

API

  1. add - Push an item to the back of the queue
  2. remove - Remove an item from the start of the queue
  3. peek - Show the last item pushed into the queue
  4. clear - Empty the queue
  5. size - Get the current size of the queue

Creating a Queue

Simple Queue

Simple queue, as the name suggests, is a FIFO data structure in which we can push the data from the back and pop it from the front.

We are going to skip the pleasantries and go straight to using closures for creating the Queue, details are explained in the previous article here

var Queue = (() => {
    let items = [];

    class Queue {

        constructor() {

        }

        add(element) {
            items.push(element);
        }

        remove() {
            return items.shift();
        }

        peek() {
            return items[items.length - 1];
        }

        clear() {
            items = [];
        }

        size() {
            return items.length;
        }
    }

    return Queue;
})();

which when executed returns

var queue = new Queue();
queue.add(10);
queue.add(20);

console.log(queue.items); // prints undefined

console.log(queue.size()); // prints 2

console.log(queue.remove()); // prints 10

console.log(queue.size()); // prints 1

queue.clear();

console.log(queue.size()); // prints 0

Circular Queue

The difference between a Circular queue and a simple queue is that the back of the queue is followed by the front of the queue.

That being said, they arent functionally different. They still perform the same operations which produce the same results, then you might be wondering where exactly do they differ and why does it matter if the end result is the same.

Short Answer:

It does not matter a lot while using native push, pop operations in JavaScript whether you use Simple or Circular Queues as memory allocation is non contiguous and the size of the queues is dynamic. But dont worry yet, check out the performance section below which shows how you can enhance the performance of you queues by a huge margin.

Long Answer:

In JavaScript, the memory allocation is non contiguous i.e random memory locations are assigned to variables. Even if you create an empty array and insert two elements at positions 0 and 1 there is no guarantee that they would be assigned memory locations next to each other (aka contiguous memory).

But why does this matter? Because in some programming languages, the memory locations are contiguous. So when creating the Queue and performing operations such as remove we need to worry about moving the remaining elements to point to the updated front instead of null thus increasing the number of operations and its a memory hit too unless your queue has unlimited/dynamic number of slots.

Now imagine a circular queue, because of the circular nature, this queue has a fixed number of memory locations and when an element is removed or added, all we need to do is update the pointers to point to the new front or back instead of the old front or back whose value could now be null in case of remove operation. This new open memory slot can be filled with a new element via add operation. So in circular queues you get to reuse memory locations and reduce the number of operations that are performed which makes it incredibely fast.

Priority Queue

Priority Queue is operationally similar to the simple queues i.e. they support them same API, but there is a small addition to the data that they hold. Along with the element (a.k.a your data) we also persist a priority which is just a number indicating the priority of your element in the queue.

    {
        "element": data,
        "priority": value
    }

When elements are being added/removed from a priority queue, it is done so in groups. Lets say you have 2 elements A, E with priority 1, 2 elements B, D with priority 2 and 2 more elements C, F with priority 3.

And when you try to add a new element G of priority 1, then it gets added to the back of all the elements with priority 1 and when you pop from this queue, the element at the front with the highest priority will be returned.

Let us translate that into some code now, the most critical of the change is going to be to the add method. For a simple queue we simply push the element into the queue

        add(element) {
            items.push(element);
        }

We now need to perform an additional check where we determine the position of the new element first based on the priority.

Your add method will have to be modified to account for this change. So instead of having a plain old push method, we change it as follows

        add(newEl) {
            items.push(element);
            for(let [i,v] of items.entries()) {
              if(newEl.priority > v.priority) {
                items.splice(i-1, 0, newEl);
              }
            } 
        }

Ofcourse this is for a Min Priority Queue where the priority 1 is considered higher than 2 which is considered higher than 3. There is another variant called Max Priority Queue in which the inverse is true i.e. priority 3 is considered higher than 2 which is considered higher than 1. For Max Priority Queue the above add method would look different as our if condition to check the priority would now need to be reversed.

Dequeue

Double Ended queue a.k.a Dequeue is also similar to a simple queue except that the add and remove can be done from either the front or the back of the queue. This is basically the same API as your array and I can show you an example of the class that would provide this functionality, but lets do one better and see how we can implement all the above discussed using a circular queue and make it as performant as possible.

Performance

Performance matters. Period. Thats why we are going to implement a double ended circular queue in a very efficient matter.

For the ease of explanation we tend to use the native array operations such as push, pop, shift and unshift etc. These work for most of the cases. For example the unshift operation has O(N) time complexity, which at first does not seem that bad, but think of these operations on an array with 10000 or even 100000 elements which can be slower than one might think.

What we generally tend to overlook is the concept of sparse arrays in JavaScript. Although this is an under the hood implementation and could keep changing every now and then. Most of the times JavaScript arrays are dense and can easily become sparse if not handled properly. A simple way to test this is to create an array as follows

Example 1:

    const a = [undefined, undefined, 10];

and when you log it you see the same

[undefined, undefined, 10];

Now create an array like this

Example 2:

    const b = [];
    b[3] = 10; // hole as we missed out index 0,1,2

and when you log it you see same

[undefined x 3, 10];

This is interesting as it shows the difference between dense (example 1) and sparse (example 2) behaviour of the JavaScript arrays. When you create these dense arrays the elements of the array are known to be of specific values and these values are known at the time of initialization which gives JavaScript an option of keeping these values in contiguous memory.

But that is unlikely in the case of the sparse arrays since we create an array and dynamically add values (with holes) the browsers revert to use a hash map internally to save them, there is very little chance of these values being in contiguous memory locations thus making all the native operations less performant.

For example the corresponding V8 code for implementation of arrays native push method is here and here.

Our new goal now is to create a circular queue which holds our dense array of data and performs all the necessary queue operations without having to use the native array operations.

Here for the sake of simplicity of the example, the size of the of the queue has been limited to 1024 but this can be easily made dynamic by adjusting the size if necessary while performing any of the operations on the queue.

class CircularDequeue {
    constructor() {
        // pseudo realistic 2^x value
        this._size = 1024;
        this._length = 0;
        this._front = 0;
        this._data = [];
    }

    push (item) {
        // get the length of the array
        var length = this._length;

        // calculate the end
        var i = (this._front + length) & (this._size - 1);

        // assign value to the current end of the data
        this._data[i] = item;

        // increment length for quick look up
        this._length = length + 1;

        // return new length
        return length + 1;
    }

    pop () {
        // get the length of the array
        var length = this._length;

        // calculate the end
        var i = (this._front + length - 1) & (this._size - 1);

        // copy the value to return
        var ret = this._data[i];

        // remove the value from data
        this._data[i] = undefined;

        // reduce length for look up
        this._length = length - 1;

        // return value
        return ret;
    }

    shift () {
        // get the current front of queue
        var front = this._front;

        // capture return value
        var ret = this._data[front];

        // reset value in the data
        this._data[front] = undefined;

        // calculate the new front of the queue
        this._front = (front + 1) & (this._size - 1);

        // reduce the size
        this._length = this._length - 1;

        // return the value
        return ret;

    }

    unshift (item) {
        // get the size
        var size = this._size;

        // calculate the new front
        var i = (((( this._front - 1 ) & ( size - 1) ) ^ size ) - size );

        // add the item
        this._data[i] = item;

        // increment the length
        this._length = this._length + 1;

        // update the new front
        this._front = i;

        // return the acknowldgement of the addition of the new item
        return this._length;
    }
}

Ran this against the standard array to check the performance gains and was not disappointed, for 1000 points, the circular queue was an improvement by a big margin atleast for the push and unshift operations while being second for the pop and the shift operations.

And there it is, a high performance implementation of a double ended circular queue which can be used to perform all operations mentioned in this article.

Example

Now that we have the queue built and ready to go, let us see how we can employ this technique in server side web development.

We are going to build a small part of the messaging queue of a chat application. As the name suggests, we will be receiving a bunch of messages which are a part of a conversation.

We will also be tracking the errors that may occur when we are trying to forward these messages to their intended recepients in our queue.

The idea for the implementation is very straight forward, catch the failures per conversation and add them to a queue. Try to resend these in the order in which they were received and remove when successfully resent.

To do this create an express application first, if you have nodejs installed, just run the following commands

    npm init
    // answer the basic questions to build your package.json
    npm install --save express
    npm install --save body-parser

We will be using body-parser to make the body of the requests easily parsable.

Initial Setup

Create the server.js file in your apps root folder.

    touch server.js

And then import the previously installed node modules for consumption

    var express = require('express');
    var app = express();
    var Queue = require('./queue-es6');
    var bodyParser = require('body-parser');
    var failedMessageQueue = new Queue();

    app.use(bodyParser.json());
    app.use(bodyParser.urlencoded({ extended: true }));

    app.listen(3000, function () {
        console.log('Chat Application listening on port 3000!')
    });

Now that we have the set up out of the way, first we would need an endpoint to which our chat users can post the messages

    app.post('/send-message', function (req, res) {
        res.send('OK!');
    });

Next step is just to add the functionality for forwarding the message to its recepient, checking for failures and triggering failure protocol.

forwarding the message to its recepient, checking for failures

    // try to send it to intended recepient
    sendMessage(req.body)
        .then(function() {
            console.log("SUCCESS: " + msg.message);
            res.send('OK!')
        }, function(msg) {
            console.log('FAILURE: ' + msg.message);
            failedMessageQueue.add(msg);
            // trigger failure protocol
            triggerFailureProtocol();
            // send failure back
            res.status(500).send('Not OK!')
        });

failure protocol

        var msg = failedMessageQueue.front();
        sendMessage(msg)
            .then(function() {
                console.log("Failure Protocol SUCCESS: " + msg.message);
                failedMessageQueue.remove();
            }, function(msg) {
                console.log('Failure Protocol FAILURE: ' + msg.message);
                //retry failure protocol
                triggerFailureProtocol();
            });

Important difference between sending the message to the recepient and the failure protocol handler is that we dont want to remove the message from the failed messages queue until the message is sent successfully.

Conclusion

Although in some of the cases queues may seem like an overkill, they are actually more than just the simple API interface and performance boosters. Queues (like all the other Data Structures) provide a more symantic way of organizing your code and enhances the readability of your overall application.

The full code sample can be accessed here and the example is posted here

The performance benchmark is available here

Helpful links

https://jsperf.com/array-push-vs-unshift-vs-direct-assignment/42

https://github.com/codemix/fast.js#how

Kashyap Mukkamala

I'm a Developer Advocate at Egen Solutions Inc, I fiddle around with JavaScript, Angular, Ionic & NativeScript during the day. Devoted Brogrammer.