Queue Implementation using Linked List  

Introduction

In our previous article we saw how to implement queue using array . Due to some limitations of array , it is not the memory efficient way to implement the queue .
  So , in this article we are going to deeply dive into the concept of  implementing the queue with linked list .

Actual Implementation 
  
Here we are using singly linked list to implement the queue . 
A node of linked list has two fields , a data field in which we put our data and the address field which holds the address of next node .

 We have to maintain two pointers ,Front and Rear to keep track of insertion and deletion . 
The graphical representation of queue using linked list is shown below .
Queue using linked list

Operations on Queue 
Is_Empty() 
This function is used to check whether the queue is empty or not . 
It returns true if queue is empty , else returns false .

bool IsEmpty()
{
    if (Front==NULL)

        return true;
  
    else
        return false;
}

Enqueue(int value)
Enqueue is used to insert the data element in queue at rear end .
It takes one argument , int or float or char .
The enqueue operation in queue is better understood by following example . 
Suppose we have to enqueue three elements into the queue of linked list .
Initially Front = Rear = NULL . 
 
When Enqueue(10) is called , both Front and Rear start pointing first node .
Enqueue(10)
 When Enqueue(20) is called ,
When Enqueue(30) is called , 
In the same way the insertion occur in queue .   

Code for enqueue() :
void enqueue(int value)
{
    node *newNode = createNode(value);
    if(Front==NULL)
    {
        Front = newNode;
        Rear = newNode;
    }
    else
    {
        Rear->next = newNode;
        Rear = newNode;
    }
}

 Dequeue()
Dequeue is used to delete the elements from  front end of queue . 
It returns the deleted element to the user .
It does not take any parameter . 
Let's suppose that we have above queue and we have to dequeue all the elements of it .
So ,when we call dequeue()  
Again when we call dequeue() , 
When dequeue is called ,


Code for Dequeue():

int dequeue()
{
    int x = Front->data;
    node *temp = Front;
    if(Front==Rear)
    {
        Front = NULL;
        Rear =  NULL;
    }
    else
    {
        Front = Front->next;

    }
    delete(temp);
    return x;
}

 

  # Code for Queue using Linked List

Download the code here
#include<iostream>
using namespace std;

struct node
{
    int data;
    node *next;
};

node *Front ,*Rear;

bool IsEmpty();
void enqueue(int value);
int dequeue();
void display();
node *createNode(int value);

int main()
{
    int option,num;
    Front = NULL;
    Rear = NULL;

    cout<<"\t\t\tQueue Implementation using Linked List \n";
    do{
        cout<<"-----------------------------------------------------------------------------------\n";
        cout<<"\t\t  1. Enqueue\n";
        cout<<"\t\t  2. Dequeue\n";
        cout<<"\t\t  3. Display\n";
        cout<<"\t\t  4. Exit\n";
        cout<<"Enter your choise : ";
        cin>>option;

        switch(option)
        {
            case 1:
                    cout<<"Enter the data to enqueue : ";
                    cin>>num;
                    enqueue(num);
            break;
            case 2:
                    if(IsEmpty())
                        cout<<"\t\t\tCannot delete the element ! Queue is empty !\n";
                    else
                    {
                        cout<<"\t\t\tDeleted element is : "<<dequeue()<<endl;
                    }
            break;
            case 3:
                  if (IsEmpty())
                        cout<<"\t\t\tOops ! No elements to display ! Queue is Empty \n";
                    else
                    {
                        cout<<"\t\t\tDisplaying the elements : "<<endl;
                        display();
                    }
            break;
        }

    }while(option<=3 && option>=1);
}

bool IsEmpty()
{
    if (Front==NULL)

        return true;
   
    else
        return false;
}

node *createNode(int value)
{
    node *temp = new node;
    temp->data = value;
    temp->next = NULL;
    return temp;
}
void enqueue(int value)
{
    node *newNode = createNode(value);
    if (Front==NULL)
    {
        Front = newNode;
        Rear = newNode;
    }
    else
    {
        Rear->next = newNode;
        Rear = newNode;
    }
}
int dequeue()
{
    int x = Front->data;
    node *temp = Front;
    if (Front==Rear)
    {
        Front = NULL;
        Rear =  NULL;
    }
   else
    {
        Front = Front->next;

    }
    delete(temp);
    return x;
}
void display()
{
    node *iterator = Front ;
    while(iterator!=NULL)
    {
        cout<<"\t\t"<<iterator->data<<endl;
        iterator = iterator->next;
    }
}


OutPut


    Queue Implementation using Linked List
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 1
Enter the data to enqueue : 10
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 1
Enter the data to enqueue : 20
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 1
Enter the data to enqueue : 30
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 3
            Displaying the elements :
        10
        20
        30
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 2
            Deleted element is : 10
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 2
            Deleted element is : 20
-----------------------------------------------------------------------------------
          1. Enqueue
          2. Dequeue
          3. Display
          4. Exit
Enter your choise : 2
            Deleted element is : 30

 

Advantages of Queue using Linked list
  1. Efficient utilization of memory .
  2. No need to know the size of queue in advance .
  3. Dynamic memory allocation .
Disadvantages Queue using Linked list 
  1. Implementation requires more memory as along with data , address is also needs to store. 
  2. As nodes are allocated dynamically in memory , the processing time is bit more than array . 
    Conclusion :
     Queue can be efficiently implemented using linked .