  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 12, 2022 by Ria Pathak ### 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
if (tail == NULL) {
return;
}

// Insert the new node after 'tail'
tail->next = new_node;
// update the 'tail' with new node's
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.
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.
return;
// decrement the 'size' by one
--size;

// If head becomes NULL, then
// change tail also as 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;
}
```

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

```#include
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
};

class Queue {
public:
int size;
Queue()
{
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
if (tail == NULL) {
return;
}

// Insert the new node after 'tail'
tail->next = new_node;
// update the 'tail' with new node's
tail = new_node;
}

// Function to remove
// a key from given queue q
void deQueue()
{
// If queue is empty, return NULL.
return;
// decrement the 'size' by one
--size;

// If head becomes NULL, then
// change tail also as 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;
}
// 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.

[forminator_quiz id=”5278″]

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.