C program for implementing Queue ADT using singly linked list explained, How to implement Queue ADT using singly linked list? How to implement Queue data structure using linear linked list in C?
C Program for implementation of Queue ADT using linked list
#include<stdio.h>
#include <stdlib.h>
struct QueueNode //Node
definition
{
int data; //To store the
data element
struct QueueNode *next; //To
store the pointer to the next node
};
typedef struct QueueNode node;
/* Next two statements declare front and
rear pointers to point the first and the last elements respectively. They are
set to NULL initially. */
node *front = NULL;
node *rear = NULL; //rear
node* createNode() //Function
createNode to create a new node
{
node *temp;
temp = (node *) malloc(sizeof(node)) ; //Dynamic memory allocation
printf("\n Enter data to enqueue : ");
scanf("%d", &temp -> data); //Reads the data for new element enqueued
temp -> next = NULL; //sets
the next of new node with NULL
return temp;
}
void enQueue() //To insert
an element into the queue
{
node *newnode;
newnode= createNode(); //Calls
the createNode function
if(front == NULL) //if
front is NULL, the queue is empty
{
/* For the first time insertion, we
initialize the front and rear pointers to point to
the newly created node by assigning the address of first element of newnode to
front and rear in the following two statements */
front = newnode;
rear = newnode;
}
else
{
/* If the queue has nodes in it, the
current rear
node’s next
pointer, ie rear->next is
assigned with the address stored in new node. And, the new node becomes the new
rear. */
rear -> next = newnode; //here
newnode has the starting address of
first element in newnode
rear=newnode;
}
printf("\n\n Data added to the Queue..");
}
void deQueue()
{
node *temp;
if(front == NULL)
{
printf("\n\n\t Empty Queue..");
return;
}
/* To dequeue a node, the front pointer has to be set
to point to the next node in the queue. (In array implementation, we have
incremented front with front + 1). This can be done by
assigning the current front
node’s next
element, ie., front->next to
new front. */
temp = front; //current front is stored in a temporary variable
front = front -> next; //what
front points to is stored in front
printf("\n\n\t Deleted element from queue is %d
", temp -> data);
free(temp); //free
(de-allocate) the memory used for temp
}
void displayQ()
{
node *temp;
if(front == NULL)
{
printf("\n\n\t\t Empty Queue ");
}
else
{
/* From front node, displays the data, ie temp->data and move the pointer to the
next node and so on */
temp = front;
printf("\n\n\n\t\t Elements in the Queue are:
");
while(temp != NULL)
{
printf("%5d ", temp -> data); //displays the data in current node
temp = temp -> next; //Assign
the current node with the address store in the next pointer
}
}
}
int main()
{
int n;
while(1)
{
printf("\n\n Linked list implementation of Queue
operations ");
printf("\n
----------------------------------------------\n");
printf("\n 1. Enqueue ");
printf("\n 2. Dequeue ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Enter your choice: ");
scanf("%d", &n);
switch(n)
{
case 1 :
enQueue();
break;
case 2 :
deQueue();
break;
case 3 :
displayQ();
break;
case 4:
return;
}
}
}
***************