Data structures — Queues

Queues are a data structure that store information in the form of a list, allowing only adding and removing elements under a FIFO pattern (first in, first out). In queues, elements can’t be added or removed out of order, they always have to follow the FIFO pattern.

Some examples of queues usage are:

• Background tasks.
• Printing/task processing.

There’s more than one way to implement a stack, but probably the simplest is using an array with its push and shift methods. If we only use push and shift for adding and deleting elements, we’ll always follow the FIFO pattern and so operating over it like a queue.

Another way is to implement it like a linked list, which may look like this:

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}
class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    dequeue(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

The big O of queue methods is the following:

• Insertion — O(1)
• Removal — O(1)
• Searching — O(n)
• Access — O(n)