What is a Queue

Queue is a data structure that follow FIFO - the first thing added is the first thing returned

Que operations included

• enqueue

• dequeue

• peek

• length

Where Queue is used

• Network protocols

• Task Scheduling ...

How to implement Queue

class Queue {
    constructor() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    // queue items arrange from headIndex to tailIndex - 1
    enqueue(val) {
        // if queue is not empty?
        this.items[this.tailIndex] = val;
        this.tailIndex++;
    }
    dequeue() {
        this.#validate();

        const item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;

        return item;
    }

    // first added item
    peek() {
        this.#validate();
        return this.items[this.headIndex];
    }

    get length() {
        return this.tailIndex - this.headIndex;
    }

    #validate() {
        // head = tail => no between => empty
        if (this.headIndex === this.tailIndex) return null;
    }
}
// Testing
const queue = new Queue();

queue.enqueue('hello');

queue.enqueue('from');
queue.enqueue('hanoi');

queue.dequeue();

console.log(queue);
console.log(queue.peek());
console.log(queue.length);

Big O of Queue

Time complexity: all operations of Queue should be O(1)

Space complexity: O(1)