A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Implementing queue using arrays:

1. Using the push and shift methods:

    // push/shift
    var queue = [];
    queue.push(1);
    queue.push(2);
    queue.push(3);
   
    // queue => [1, 2, 3]
   
    queue.shift(); // 1
    queue.shift(); // 2
   

2. Using the unshift and pop methods:

    // unshift/pop
    var queue = [];
    queue.unshift(1);
    queue.unshift(2);
    queue.unshift(3);
   
    // queue => [3, 2, 1]
   
    queue.pop() // 1
    queue.pop() // 2
   

---

Creating a queue using a linked list:

Todos:

1. Enqueue

2. Dequeue

Creating a node: It contains a value and a pointer.

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

Queue class: It contains the first value, last value, and length.

class queue {
    constructor() {
        this.first = null;
        this.last = null;
        this.length = 0;
    }
}

Enqueue: adding to the end of the queue

1. This function accepts some value.

2. Create a new node using that value passed in the function.

3. If there are no nodes in the queue, set this node to be the first and last property of the queue.

4. Otherwise, set the next property on the current last to be that node, then set the last property of the queue to be that node.

5. Increment the length of the queue by one.

    enqueue(val) {
            let newNode = new Node(val);
            if(!this.first) {
                this.first = newNode;
                this.last = newNode;
            } else {
                this.last.next = newNode;
                this.last = newNode;
            }
            return ++this.length;
        }
   

Dequeue: removing the node from the beginning of the queue.

1. If there is no first property then return null.

2. Store the first property in a variable.

3. See if the first is the same as the last (checking if there’s only one node in the queue), and set the first and last to be null.

4. If there is more than one node, set the first property to be the next property of the first.

5. Decrement the size by one.

6. Return the value of the node dequeued.

    dequeue() {
            if(!this.first) return null;
            let temp = this.first;
            if(this.first === this.last) {
                this.first = null;
                this.last = null;
            }
   
            this.first = this.first.next;
            this.length--;
            return temp.val;
        }
   

---

Time Complexity of a Queue:

• Access: O(n)

• Search: O(n)

• Insertion: O(1)

• Removal: O(1)