Queue Using Linked List

The major problem with the queue implemented using an array is, It will work for an only fixed number of data values. That means, the amount of data must be specified at the beginning itself. Queue using an array is not suitable when we don't know the size of data which we are going to use. A queue data structure can be implemented using a linked list data structure. The queue which is implemented using a linked list can work for an unlimited number of values. That means, queue using linked list can work for the variable size of data (No need to fix the size at the beginning of the implementation). The Queue implemented using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first node is always pointed by 'front'.

Example

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.

Operations

To implement queue using linked list, we need to set the following things before implementing actual operations.

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
• Step 4 - Implement the main method by displaying Menu of list of operations and make suitable function calls in the main method to perform user selected operation.

enQueue(value) - Inserting an element into the Queue

We can use the following steps to insert a new node into the queue...

• Step 1 - Create a ptr with given value and set ptr -> next' to NULL.
• Step 2 - Check whether queue is Empty (rear == NULL)
• Step 3 - If it is Empty then, set front = ptr and rear = ptr
• Step 4 - If it is Not Empty then, set rear -> next = ptr and rear = ptr.

deQueue() - Deleting an Element from Queue

We can use the following steps to delete a node from the queue...

• Step 1 - Check whether queue is Empty (front == NULL).
• Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function
• Step 3 - If it is Not Empty then, define a Node pointer 'ptr' and set it to 'front'.
• Step 4 - Then set 'front = front -> next' and delete 'ptr' (free(ptr)).

display() - Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...

• Step 1 - Check whether queue is Empty (front == NULL).
• Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty then, define a Node pointer ptr' and initialize with front.
• Step 4 - Display 'ptr -> data  and move it to the next node. Repeat the same until 'ptr' reaches to 'rear' (ptr -> next != NULL).
• Step 5 - Finally! Display ptr -> data ---> NULL'.

 

Implementation of Queue  using Linked List

 

    #include<stdio.h>   
    #include<stdlib.h>  
    struct node   
    {  
        int data;   
        struct node *next;  
    };  
    struct node *front;  
    struct node *rear;   
    void insert();  
    void delete();  
    void display();  
    void main ()  
    {  
        int choice;   
        while(choice != 4)   
        {     
            printf("\n*************************Main Menu*****************************\n");  
            printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");  
           printf("Enter your choice: ");
            scanf("%d",& choice);  
            switch(choice)  
            {  
                case 1:  
                insert();  
                break;  
                case 2:  
                delete();  
                break;  
                case 3:  
                display();  
                break;  
                case 4:  
                exit(0);  
                break;  
                default:   
                printf("\nWrong selection!!! Please try again!!!\n");
            }  
        }  
    }  
    void insert()  
    {  
        struct node *ptr;  
        int item;   
          
        ptr = (struct node *) malloc (sizeof(struct node));  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW\n");  
            return;  
        }  
        else  
        {   
            printf("Enter the value to be insert: ");
            scanf("%d",&item);  
            ptr -> data = item;  
            if(front == NULL)  
            {  
                front = ptr;  
                rear = ptr;   
                front -> next = NULL;  
                rear -> next = NULL;  
            }  
            else   
            {  
                rear -> next = ptr;  
                rear = ptr;  
                rear->next = NULL;  
            }
             printf("\nInsertion is Success!!!\n"); 
        }  
    }     
    void delete ()  
    {  
        struct node *ptr;  
        if(front == NULL)  
        {  
            printf("\nUNDERFLOW\n");  
            return;  
        }  
        else   
        {  
            ptr = front;  
            front = front -> next;  
            printf("\nDeleted element: %d\n", ptr->data);
            free(ptr);  
        }  
    }  
    void display()  
    {  
        struct node *ptr;  
        ptr = front;      
        if(front == NULL)  
        {  
            printf("\nEmpty queue\n");  
        }  
        else  
        {   printf("\nprinting values .....\n");  
            while(ptr->next != NULL)   
            {  
                printf("%d--->",ptr -> data);  
                ptr = ptr -> next;  
            }  
             printf("%d--->NULL\n",ptr -> data);  
        }  
    }   

 

Output