### Problem Statement

We need to implement basic functionalities of a queue using a linked list.

A queue is a linear data structure that allows elements to be added and deleted on the first in first out principle (FIFO) i.e., the element added first will be accessible before elements added after it.

#### Some basic functionalities of a queue are:

1) **enQueue** - This function takes an integer as input and adds it to the queue.

2) **deQueue** - This function deletes an element from the queue.

3) **front** - This function will give the element that is present in front of the queue.

4) **rear** - This function will give the data present at the end of the queue.

5) **size** - This function will return the number of elements in the queue.

6) **isEmpty** - This function returns true when the list is empty and returns false otherwise.

### Approach

- We will use a singly linked list to implement the queue.
- We will keep track of two pointers, i.e., the
**head**and**tail**node of the list, which will act as**front**and**rear**of the queue, respectively. - Furthermore, we need to maintain a
**size**variable as well to keep track of the present size of the list. - If we want to add an element to the list
**(enQueue operation)**, we will insert it at the end of the list, i.e., after the**tail**of the list, and the addition of an element increases the size of the queue by one. - If we want to remove an element from the list
**(deQueue operation)**, we will remove the**head**node of the list, and the removal of an element decreases the size of the queue by one.

### Queue Operations

At first, we will define a class of Queue which will contain a head pointer, a tail pointer and an integer variable named size.

#### enQueue Operation

1) First, we will create a new node having the data passed in the function while calling.

2) Then, we will increment the **size** variable by one.

3) Then, we will check if **tail** is NULL.

- If it is NULL, that means the list is empty, so we need to update the
**head**as well as the**tail**node with the newly created node and finally return. - Else, we will insert the new node after the
**tail**node as**tail->next = new_node**. - Then, we will update
**tail**with the newly created node.

##### Function Implementation

void enQueue(int x){ // create the new node with 'x' // as data Node* new_node = new Node(x); // increment the 'size' by one ++size; // When queue is empty, update // both 'head' and 'tail' if (tail == NULL) { head = tail = new_node; return; } // Insert the new node after 'tail' tail->next = new_node; // update the 'tail' with new node's // address tail = new_node; }

**Time Complexity:** O(1), as we are only changing few pointers.

#### deQueue Operation

1) If the **head** is NULL, we need to return from the function, as the list is empty and there is nothing to delete.

2) We will decrement the **size** variable by one.

3) Now, we will store the address of **head** in another variable, say **temp**.

4) Then, we need to update the **head** with **head->next**.

5) Now, If **head** is NULL, that means the list is empty so, we need to make the **tail** NULL.

6) Now, we will delete the **temp** node to free the memory used by the **temp** node.

##### Function Implementation

void deQueue(){ // If queue is empty, return NULL. if (head == NULL) return; // decrement the 'size' by one --size; // Store previous head and // move head one node ahead Node* temp = head; head = head->next; // If head becomes NULL, then // change tail also as NULL if (head == NULL) tail = NULL; delete (temp); }

**Time Complexity:** O(1), as we are only changing few pointers.

#### front Operation

1) We will check if the **size** is zero.

- If the
**size**is zero, we will simply return -1 from the function, i.e., the queue is empty as there is no node in the list. - Else, we will return the data of the
**head**node.

##### Function Implementation

int front(){ if(size == 0) return -1; return (head->data); }

**Time Complexity:** O(1), as we only checking if size is zero or not.

#### rear Operation

1) We will check if the **size** is zero.

- If the
**size**is zero, we will simply return -1 from the function, i.e., the queue is empty as there is no node in the list. - Else, we will return the data of the
**tail**node.

##### Function Implementation

int rear(){ if(size == 0) return -1; return (tail->data); }

**Time Complexity:** O(1), as we only checking if size is zero or not.

#### size Operation

- We need to simply return the
**size**from the function.

#### isEmpty Operation

- We will return true if the
**size**is zero and false otherwise.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node { public: int data; Node* next; Node(int d) { data = d; next = NULL; } }; class Queue { public: Node *head, *tail; int size; Queue() { head = tail = NULL; size = 0; } void enQueue(int x) { // create the new node with 'x' // as data Node* new_node = new Node(x); // increment the 'size' by one ++size; // When queue is empty, update // both 'head' and 'tail' if (tail == NULL) { head = tail = new_node; return; } // Insert the new node after 'tail' tail->next = new_node; // update the 'tail' with new node's // address tail = new_node; } // Function to remove // a key from given queue q void deQueue() { // If queue is empty, return NULL. if (head == NULL) return; // decrement the 'size' by one --size; // Store previous head and // move head one node ahead Node* temp = head; head = head->next; // If head becomes NULL, then // change tail also as NULL if (head == NULL) tail = NULL; delete (temp); } // this function returns true when list is empty // and returns false otherwise bool isEmpty(){ return (size==0); } // this function returns front element // of the queue int front(){ if(size == 0) return -1; return (head->data); } // this function returns rear element // of the queue int rear(){ if(size == 0) return -1; return (tail->data); } }; // Driven Program int main() { Queue list_queue; list_queue.enQueue(5); list_queue.enQueue(8); list_queue.enQueue(3); cout<<"Size of list after inserting three elements "<<(list_queue.size)<<"\n"; list_queue.deQueue(); cout<<"Front element of the list is "<

#### Output

Size of list after inserting three elements 3

Front element of the list is 8

Rear element of the list is 3

**Time Complexity:** All the above operations have a time complexity of O(1), as we are only changing few pointers in the above operation and also there is no loop in any of the above operations.

So, in this blog, we have tried to explain how you can implement a queue using Linked List most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.