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'.

Algorithm

Node structure for Queue :

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

To point the front and rear node :

    struct node *front = NULL, *rear = NULL;

Enqueue function :

Enqueue function will add the element at the end of the linked list.
Using the rear pointer, we can track the last inserted element.

Declare a new node and allocate memory for it
If front == NULL, make both front and rear points to the new node.
Otherwise,add the new node in rear->next.
make the new node as the rear node. i.e. rear = new node

        void enqueue(int val)
        {
            struct node *newNode = malloc(sizeof(struct node));
            newNode->data = val;
            newNode->next = NULL;

            //if it is the first node
            if(front == NULL && rear == NULL)
                //make both front and rear points to the new node
                front = rear = newNode;
            else
            {
                //add newnode in rear->next
                rear->next = newNode;

                //make the new node as the rear node
                rear = newNode;
            }
        }

Dequeue function :

Dequeue function will remove the first element from the queue.

Check whether the queue is empty or not
If it is the empty queue (front == NULL) We can't dequeue the element.
Otherwise, Make the front node points to the next node. i.e front = front->next; if front pointer becomes NULL, set the rear pointer also NULL. Free the front node's memory.

        void dequeue()
        {
            //used to freeing the first node after dequeue
            struct node *temp;

            if(front == NULL)
                printf("Queue is Empty. Unable to perform dequeue\n");
            else
            {
                //take backup
                temp = front;

                //make the front node points to the next node
                //logically removing the front element
                front = front->next;

                //if front == NULL, set rear = NULL
                if(front == NULL)
                    rear = NULL;

            //free the first node
            free(temp);
            }
        }

Program using C

// QUEUE USING LINKED LIST
#include<stdio.h>
#include<stdlib.h>
void insert(int);
int del ();
void display();
struct node
{
	int info;
	struct node *next;
}*front = NULL, *rear = NULL;
int main()
{
	int ch, item;
	while(1)
	{
		printf("\n1.Insert\n2.Delete\n3.Display\n4.Exit\n\nEnter your choice: ");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1:
				printf("\nEnter the item: ");
				scanf("%d",&item);
				insert(item);
				break;
			case 2: 
				item=del();
				if(item!=-1)
					printf("\nThe deleted item is: %d",item)	;
				break;
			case 3:
				display();
				break;
			case 4: exit(0);
			default: 
				printf("Invalid Choice.");		
		}
	}
}
void insert(int item)
{
	if(rear == NULL)
	{
		struct node *nw;
		rear= (struct node*) malloc (sizeof(struct node));
		rear -> info=item;
		rear -> next= NULL;
		front = rear;
	}
	else
	{
		rear -> next = (struct node*) malloc(sizeof(struct node));
		rear =rear -> next;
		rear -> info = item;
		rear -> next = NULL; 
	}
}
int del ()
{
	int item;
	struct node *ptr;
	if(front == NULL)
	{
		printf("\nQueue is empty");
		return (-1);
	}
	else
	{
		ptr= front;
		item=front -> info;
		front = front -> next;
		free(ptr);
		if(front == NULL)
	     	rear=NULL;
		return(item);
	}
}
void display()
{
	struct node *ptr = front;
	if(rear == NULL)
		printf("\nQueue is Empty");
	else
	{
		printf("\nThe Queue is : ");
		while(ptr != NULL)
		{
			printf("%d\t",ptr->info);
			ptr = ptr->next;
		}
	}
}