Queues.


Introduction to queues:-

A queue is also a linear data structure in which data is inserted from one end and removed from another end. The node where we insert the data is nothing tail or rear. The point where we remove the data is nothing but head or front. The queue is a data structure in which data which is inserted first is first to be removed. Hence queues are also called as First In First Out(FIFO) data structure.
 
We use queues in real life very regularly. For example, let’s consider we are standing in a queue for movie tickets. Whoever gets into the queue first will get the tickets first. Similarly, there are so many examples such as waiting in queue for getting into the bus or waiting in a queue to submit the application, etc. 
 
people standing in queue.

The operations performed on queues are
  1. Enqueue.
  2. Dequeue.
Here, we will use a singly linked list to implement the stack. Meanwhile, If you are not aware of the singly linked list, I have written it here. Please do check it. If you understand singly-linked lists, implementation of queues is very similar. 
 

Firstly, Let’s define a Node class to hold the data and the next node.

class Node {
    Object value;
    Node next;
    public Node(Object value) {
        super();
        this.value = value;
        this.next = null;
    }
}
public class QueueWithSinglyLinkedList {
    int length;
    Node head;
    Node tail;
    public QueueWithSinglyLinkedList() {
        super();
        this.length = 0;
        this.head = null;
        this.tail = null;
    }
}
class Node {
    constructor(value) {
        this.val = val;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.length = 0;
        this.head = null;
        this.tail = null;
    }
}

1. Enqueue:-

The Enqueue operation inserts a new data to the queue.

enqueue illustration.

The pseudocode for enqueue as follows.

enqueue pseudocode.
By following the above pseudocode let’s add enqueue function into the implementation class.
 
public Node enqueue(Object value) {
        Node newNode = new Node(value);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
            this.length += 1;
            return this.tail;
        }
        else {
            Node currentTail = this.tail;
            currentTail.next = newNode;
            this.tail = newNode;
            this.length += 1;
            return this.tail;
        }
    }
enqueue(value) {
        var newNode = new Node(value);
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode
            this.length += 1;
            return this.tail;
        }
        else {
            var currentTail = this.tail;
            currentTail.next = newNode;
            this.tail = newNode;
            this.length += 1;
            return this.tail
        }
    }

The time complexity of the enqueue operation is O(1) as we add new data to the existing tail node which is available by the variable tail.

2. Dequeue:-

To remove the data from the queue we use the dequeue operation. Remember that we need to remove the current head node as it is inserted first in the enqueue operation.
dequeue illustration.

The pseudocode for the same is as shown below.

dequeue pseudocode.
 
public Object deQueue() {
        if (this.length == 0) {
            return null;
        }
        if (this.length == 1) {
            Node currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        else {
            Node currentHead = this.head;
            this.head = currentHead.next;
            this.length -= 1;
            return currentHead.value;
        }
    }
deQueue() {
        if (this.length === 0) {
            return null;
        }
        if (this.length === 1) {
            var currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        else {
            var currentHead = this.head;
            this.head = currentHead.next;
            this.length -= 1;
            return currentHead.value;
        }
    }

The time complexity of the dequeue operation is also O(1) as we removed the current head and make the next element as the new head node.

Some of the real life applications of the queues are

  1. running a set of background tasks
  2. uploading resources.
  3. Printing
  4. Sending communication(messages, push notifications, emails etc) to multiple customers by adding them to the queue.