Queues - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki

Queues

• https://initjs.org/implement-a-queue-in-javascript-de306a8821c

How Work?

• A queue is like a line at a restaurant. It’s “first in, first out” (FIFO), which means that the item that was put in the queue longest ago is the first item that comes out. “First come, first served.”
• Most use-cases for a queue are involved with building or utilizing other data structures. One example could be in breadth-first traversal of a tree.

Skeleton Code

class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class Queue {
    constructor() {
        this.storage = {}
        this.count = 0
        this.lowestCount = 0
    }

    // methods to implement:

    // enqueue(value)
    // dequeue()
    // front()
    // isEmpty()
    // size()
}

Methods

// Adds a value to the end of the chain
Enqueue(value) {
    // Check to see if value is defined
    if (value) {
        this.storage[this.count] = value;
        this.count++;
    }
}

// Removes a value from the beginning of the chain
Dequeue() {
    // Check to see if queue is empty
    if (this.count - this.lowestCount === 0) {
        return undefined;
    }

    var result = this.storage[this.lowestCount];
    delete this.storage[this.lowestCount];
    this.lowestCount++;
    return result;
}

// Returns the length of the queue
Size() {
    return this.count - this.lowestCount;
}

Example

class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class Queue {
    constructor() {
        this.root = null
        this.tail = null
        this.length = 0
    }
    
    
    enqueue(value) {
    let node = new Node(value);
        if (!this.root) {
            this.root = node;
            this.tail = node;
        }
        else {
            this.tail.next = node;
            this.tail = this.tail.next;
        }
        this.length++
  }
    
    
    dequeue() {
        if (!this.root) {
            return null
        }

        this.length--
        const dequeued = this.root.value
        this.root = this.root.next
        return dequeued
    }
    
    
    front() {
        let first = this.root.value;
        return first;
    }
    
    
    size() {
        return this.length;
    }
    
    isEmpty() {
        if (!this.root) {
            return true;
        }
    }