# 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.

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.

The pseudocode for enqueue as follows.

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.

The pseudocode for the same is as shown below.

`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;        }    }`