## # Queue using linked list

• Queue is a linear data structure which follows FIFO i.e. First-In-First-Out method.

• The two ends of a queue are called Front and Rear, where Insertion always takes place at the Rear and the elements are accessed or removed from the Front.

• While implementing queues using arrays:

1. We cannot increase the size of array, if we have more elements to insert than the capacity of array.
2. If we create a very large array, we will be wasting a lot of memory space.
• Therefore if we implement Queue using Linked list we can solve these problems, as in Linked list Nodes are created dynamically as an when required.

• So using a linked list we can create a Queue of variable size and depending on our need we can increase or decrease the size of the queue.

• Thus instead of using the head pointer with Linked List, we will use two pointers, `front` and `rear` to keep track of both ends of the list, so that we can perfrom all the operations in O(1).

### # Source Code - C++

``````#include <iostream>
using namespace std;

// Structure of Node.
struct Node
{
int data;

};

Node *front = NULL;
Node *rear = NULL;

//Function to check if queue is empty or not
bool isempty()
{
if(front == NULL && rear == NULL)
return true;
else
return false;
}

//function to enter elements in queue
void enqueue ( int value )
{
Node *ptr = new Node();
ptr->data= value;

//If inserting the first element/node
if( front == NULL )
{
front = ptr;
rear = ptr;
}
else
{
rear = ptr;
}
}

//function to delete/remove element from queue
void dequeue ( )
{
if( isempty() )
cout<<"Queue is empty\n";
else
//only one element/node in queue.
if( front == rear)
{
free(front);
front = rear = NULL;
}
else
{
Node *ptr = front;
free(ptr);
}
}

//function to show the element at front
void showfront( )
{
if( isempty())
cout<<"Queue is empty\n";
else
cout<<"element at front is:"<<front->data;
}

//function to display queue
void displayQueue()
{
if (isempty())
cout<<"Queue is empty\n";
else
{
Node *ptr = front;
while( ptr !=NULL)
{
cout<<ptr->data<<" ";
}
}
}

//Main Function
int main()
{
int choice, flag=1, value;
while( flag == 1)
{
cout<<"\n1.enqueue 2.dequeue 3.showfront 4.displayQueue 5.exit\n";
cin>>choice;
switch (choice)
{
case 1: cout<<"Enter Value:\n";
cin>>value;
enqueue(value);
break;
case 2: dequeue();
break;
case 3: showfront();
break;
case 4: displayQueue();
break;
case 5: flag = 0;
break;
}
}

return 0;
}
``````

Time Complexity - Each Operation is O(1)