# 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() {

}

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();

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.

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.

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 );

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
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);
// 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