Queues

The Queue data structure
- First In First Out (FIFO)
Creating a queue

function Queue(){
    let items = [];
    this.enqueue = function(element){
        items.push(element);
    }
    this.dequeue = function(){
        return items.shift()
    }
    this.front = function(){
        return items[0];
    }
    this.isEmpty = function(){
        return items.length === 0;
    }
    this.size = function(){
        return items.length;
    }
    this.print = function(){
        console.log(items.toString());
    }
}

The Queue class using ES 6 syntax

let Queue2 = (function() {
    const items = new WeakMap();

    class Queue2 {
        constructor (){
            items.set(this, []);
        }
        enqueue(element){
            let q = items.get(this);
            q.push(element);
        }
        dequeue() {
            let q = items.get(this);
            let r = q.shift();
            return r;
        }
        front() {
            let q = items.get(this);
            return q[0]
        }
        isEmpty() {
            let q = items.get(this);
            return items.length === 0;
        }
        size() {
            let q = items.get(this);
            return q.length; 
        }
        print() {
            let q = items.get(this);
            console.log(q.toString());
        }
    }
})();

The priority queue
- Elements are added and removed based on a priority
- Two strategies to implement a priority queue
  - Set the priority and add the element at the correct position
  - Or queue the elements as they are and remove them according to the priority

// add the elements at their corret position and dequeue them by default
// this is a min priority queue
// lower priority means higher priority

function PriorityQueue(){
    let items = [];
    function QueueElement (element, priority){
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function(element, priority){
        let queueElement = new QueueElement(element, priority);

        let added = false;
        for(let i = 0; i< items.length; i++){
            if(queueElement.priority < items[i].priority){
                items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }
        if (!added) {
            items.push(queueElement);
        }
    };
    this.print = function(){
        for(let i = 0; i<items.legnth; i++){
            console.log(`${items[i].element} - ${items[i].priority}`);
        }
    };

    this.dequeue = function(){
        return items.shift().element;
    };
    this.front = function(){
        return items[0].element;
    };
    this.isEmpty = function(){
        return items.length === 0;
    };
    this.size = function(){
        return items.length;
    }
}

The circular queue -The Hot Potato Game)

function hotPotato ( nameList, num){
    let queue = new Queue();

    for (let i = 0, length = nameList.length; i < length; i++){
        queue.enqueue(nameList[i]);
    }

    let eliminated = '';
    while ( queue.size() > 1){
        for(let i = 0; i < num; i ++){
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log( eliminated + ' was eliminated from the Hot Potato game.');
    }
   return queue.dequeue(); // the winner
}

JavaScript task queues
- When we open a new tab in the browser, a task queue is created.
- Only a single thread handles all the tasks for a single tab, and it is called an event loop.