Write a C Program to Implement Queue using Linked List (Pointer)

by

Aim:

Write a C Program to Implement a Stack Using Linked List (Pointer).

Theory:

Linked List Implementation of a Queue:

      We go for a linked list implementation of a queue rather than an array implementation because of the run time memory allocation feature of linked lists. In this implementation we make a head pointer and make it point to the first created node in the stack. Whenever an element is enqueued into the queue, a new node is created at the end of the linked list and the element is kept in that node. Whenever a dequeue operation is performed on the queue, the head pointer is made to point to the node, next to the one that it is currently pointing to.

Insertion:

HEAD                        prev                                               newItem

NULL

Deletion:

Before Deletion:

After Deletion

Algorithm:

  • step 1:Make FRONT point to the new node
  • step 2:Make REAR  point to the new node
  • step 3:Exit
  • step 4:Make the next field of REAR point to the new node.
  • step 5:Make REAR point to the new node.

Algorithm for delete:

  • step 1:If the queue is empty: // FRONT = NULL
  • step 2: Display “Queue empty”
  • step 3:Exit
  • step 4:Mark the node marked FRONT as current
  • step 5:Make FRONT point to the next node in its sequence
  • step 6:Release the memory for the node marked as current

Program:

#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;
void enq(int data);
void deq();
void display();
void create();
int count = 0; 
void main()
{
int no, ch, e,i=0;
 
printf("\n 1 - Enque");
printf("\n 2 - Deque");
printf("\n 4 - Exit");
printf("\n 3 - Display");
create();
while (i!=1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
display();
break;
case 4:
i= 1;
break;
default:
printf("Wrong choice, Please enter correct choice  ");
break;
}
}
}
void create()
{
front = rear = NULL;
}
void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;
rear = temp;
}    
}
void display()
{
front1 = front;
if ((front1 == NULL) && (rear == NULL))
{
printf("Queue is empty");
return;
}
while (front1 != rear)
{
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}
void deq()
{
front1 = front;
if (front1 == NULL)
{
printf("\n Error: Trying to display elements from empty queue");
return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
free(front);
front = front1;
}
else
{
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
}

Execution:

Input:
1 45 1 55 1 77 2 3 4

Output:

 1 - Enque
 2 - Deque
 4 - Exit
 3 - Display
 Enter choice : Enter data : 
 Enter choice : Enter data : 
 Enter choice : Enter data : 
 Enter choice : 
 Dequed value : 45
 Enter choice : 55 77
 Enter choice :

Result:

Thus, Implement Queue using linked list (pointer) was executed successfully.

Leave a Comment