Data structure tutorial 8: Queue Data Structure implementation using linked list in C

In this chapter we shall learn about below topics:

In previous chapter we have seen how to implement queue using arrays. In this chapter we shall see how to implement queue using linked list [LL].

One major implementation difference here is that, instead of taking 2 pointers like “rear” and “front”, using LL we can manage using one “head” pointer, that will always point to the start of the list. And manipulate using that pointer.

We shall see how we insert and delete elements from queue from below steps.

We know that we insert elements at the rear end of the queue.

Below are the steps to perform inserting elements into queue.

Step 1: Create a temp node.

Step 2: If the list is empty, then make it a head node.

Step 3: If the list is not empty, take a “curr” pointer and navigate till the end of the list.

Step 4: Then point the “next” pointer of “curr” to the “temp” node.

Below images will show the steps:

Creating a temp node

Taking a “curr” pointer and navigating to the end of Queue

Point the “next” of curr to the “temp” node.

To delete an element from the front end of the queue we perform below steps.

Step 1: Take a temp pointer to the head of the list, so that we don’t loose the head pointer.

Step 2: Move the head pointer to the next element.

Step 3: Delete the node pointed by temp pointer and free the memory to avoid memory leak.

Below images will show you the steps:

Assign a temp pointer to the head pointer.

Move the head pointer to the next node.

Delete the node hold by temp pointer

#include<stdio.h>
#include<stdlib.h> //for memory allocation functions
 
//structure to hold queue elements
struct node
{
	int data;
	struct node *next;
	
};
 
//global head pointer for easy access
struct node *head = NULL;
 
// inserting elements into the queue is called as enqueue
void enqueue(int value)
{
	//if the element entered is the first element, then it will be the head element
	if(head == NULL)
	{
		struct node *temp;
		temp = (struct node*)malloc(sizeof(struct node));
		temp->data = value;
		temp->next = NULL;
		head = temp;
	}
 
	//else navigate to the rear end of the queue
	else if(head!=NULL)
	{
		//take a temp node to hold the value
		struct node *temp;
		temp = (struct node*)malloc(sizeof(struct node));
		temp->data = value;
		temp->next = NULL;
 
		//take curr node to navigate till end of the queue
		struct node *curr;
		curr = head;
 
		while(curr->next != NULL)
		{
			curr = curr->next;
		}
		curr->next=temp;
	}
}
 
 
//deleting an element from the queue is called as dequeue
void dequeue()
{
	//take a temp pointer pointing to head
	struct node *temp = head;
 
	//move the head pointer
	head=temp->next;
 
	//free temp
	free(temp);
		
}
 
void display()
{
	struct node *temp = head;
 
	if(temp == NULL)
	{
		printf("List is Empty\n");
	}
	else
	{
		while(temp != NULL)
		{
			printf("Displaying Data:\t");
			printf("%d \n",temp->data);
			temp = temp->next;
		}
	}
}
 
int main()
{
	int choice;
	while(choice!=4)
	{
		printf("\t\tQUEUE Using LinkedList\n");
		printf("Choose One\n\n");
		printf("1)Enqueue\n");
		printf("2)Dequeue\n");
		printf("3)Display\n");
		printf("4)Logout\n\n");
		int option;
		int value;
		scanf("%d",&option);
			switch(option)
			{
				case 1:
					
					printf("Enter Number:\n");
					scanf("%d",&value);
					enqueue(value);
					break;
				case 2:
					dequeue();
					break;
				case 3:	
					display();
					break;
				case 4:
					choice=4;
					break;
				default:
				printf("Wrong Input\n\n");
						
			}
	}
	return 0;
}

		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
1
Enter Number:
1
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
1
Enter Number:
2
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
1
Enter Number:
3
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
1
Enter Number:
4
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
3
Displaying Data:	1
Displaying Data:	2
Displaying Data:	3
Displaying Data:	4
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
2
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
3
Displaying Data:	2
Displaying Data:	3
Displaying Data:	4
		QUEUE Using LinkedList
Choose One
 
1)Enqueue
2)Dequeue
3)Display
4)Logout
 
4