Priority Queue
With
Linked List using ‘C’
A priority queue can also be implemented using a
linked list data structure. In this implementation, each element in the linked
list contains a value and a priority associated with it. The elements are arranged
in the linked list based on their priorities.
Here's a high-level overview of how a priority queue
can be implemented using a linked list:
1. Initialization:
·
Create an empty linked list to
represent the priority queue.
2. Insertion:
·
When inserting an element into the
priority queue, create a new node with the given value and priority.
·
Traverse the linked list to find the
appropriate position to insert the new node based on its priority.
·
Adjust the links of the nodes to
insert the new node in the correct position.
3. Extraction:
·
To extract the element with the
highest priority from the priority queue, simply remove the head node of the
linked list.
·
The head node represents the element
with the highest priority, as it is positioned at the front of the linked list.
4. Other
Operations:
·
Additional operations can be
implemented as needed, such as checking the size of the priority queue,
accessing the element with the highest priority without removing it, or
searching for a specific element.
Compared to a binary heap implementation, a linked
list implementation of a priority queue may have different time complexities
for insertion and extraction operations. In the worst case, the insertion
operation can have a time complexity of O(n) if the new element needs to be inserted
at the end of the linked list. The extraction operation, however, has a time
complexity of O(1) since the highest priority element is always at the front of
the linked list.
It's worth noting that the choice of data structure
for implementing a priority queue depends on the specific requirements and
constraints of the application. While a linked list implementation may have
slower insertion times, it can be more flexible in terms of dynamic resizing
and memory management compared to a fixed-size array-based implementation or a
binary heap implementation.
Program:-
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
int pri;
struct
node*next;
}node;
struct
node*front=NULL;
void main()
{
int
n,choice,x;
printf("\nenter
1 to insert elements ");
printf("\nenter
2 to delete elements");
printf("\n
enter 3 to show elements");
printf("\nexit...");
//create();
while(1)
{
printf("\nenter
your choice:");
scanf("%d",&choice);
switch(choice)
{
case
1:printf("enter element to insert");
scanf("%d",&n);
printf("enter priority");
scanf("%d",&x);
insert(n,x);
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:exit(0);
default:printf("please
enter valid choice");
}
}
}
void
insert(int n,int x)
{
struct node *temp,*q;
temp=(struct node*)malloc(sizeof(struct
node));
temp->data=n;
temp->pri=x;
if(front==NULL|| x<front->pri)
{
temp->next=front;
front=temp;
}
else
{
q=front;
while(q->next!=NULL&&q->next->pri<=x)
q=q->next;
temp->next=q->next;
q->next=temp;
}
}
int
display()
{
struct node*ptr;
ptr=front;
if(front==NULL)
printf("queue is empty");
else
{
printf("queue
is :\n");
while(ptr!=NULL)
{
printf("%d %d\n",ptr->pri,ptr->data);
ptr=ptr->next;
}
}
}
int delete()
{
struct
node*temp;
if(front==NULL)
printf("queue
is empty");
else
{
temp=front;
printf("deleted
item is%d\n",temp->data);
front=front->next;
free(temp);
}
}
Output:-
0 Comments