Priority Queue
With
Queues using ‘C’
A priority queue can be implemented using a queue data
structure by incorporating additional logic to handle the priorities of the
elements. One common approach is to use multiple queues, each representing a
different priority level. Elements with more priorities are dequeued before
elements with less priorities.
Here's a high-level overview of how a priority queue
can be implemented using a queue:
1. Initialization:
·
Create multiple queues, each
representing a different priority level.
·
The number of queues can vary
depending on the number of distinct priority levels you want to support.
2. Insertion:
·
When inserting an element into the
priority queue, determine its priority level.
·
Enqueue the element into the
corresponding queue based on its priority level.
3. Extraction:
·
To extract an element from the
priority queue, start dequeuing elements from the highest priority queue.
·
If the highest priority queue is not
empty, dequeue an element from it and return it as the highest priority
element.
·
If the highest priority queue is
empty, move to the next lower priority queue and repeat the dequeuing process.
·
Continue this process until an
element is successfully dequeued or until all queues have been checked.
4. Other
Operations:
·
Additional operations can be
implemented as needed, such as checking the size of the priority queue or
peeking at the highest priority element without removing it.
The time complexity of the insertion operation in this
implementation is O(1) since elements are enqueued directly into their
respective priority queues. The extraction operation, however, depends on the
number of priority levels and the distribution of elements across those levels.
In the worst case, when all queues are empty, the time complexity is O(k),
where k is the number of priority levels.
It's important to note that the efficiency of this
implementation heavily relies on the distribution of elements across the
priority levels. If elements are evenly distributed across all priority levels,
the extraction operation will have a more balanced performance. However, if
most elements belong to a single priority level, the extraction operation may
become inefficient as it needs to traverse through the queues sequentially.
Overall, a priority queue implemented with queues can
be a simple and effective solution in scenarios where the number of priority
levels is small and the distribution of elements across those levels is
relatively balanced.
Program:-
#include<stdio.h>
#include<stdlib.h>
#define max
10
int
queue[max];
int
front,rear;
void main()
{
int
n,choice;
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);
insert(n);
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:exit(0);
default:printf("please
enter valid choice");
}
}
}
void
create()
{
front=rear=-1;
}
void
insert(n)
{
if(rear>=max-1)
{
printf("\n
queue overflow");
return;
}
if((front==-1)&&(rear==-1))
{
front++;
rear++;
queue[rear]=n;
return;
}
else
priority(n);
rear++;
}
void
priority(int n)
{
int i,j;
for(i=0;i<=rear;i++)
{
if(n>=queue[i])
{
for(j=rear+1;j>i;j--)
{
queue[j]=queue[j-1];
}
queue[i]=n;
return;
}
}
queue[i]=n;
}
void
display()
{
if((front==-1)&&(rear==-1))
{
printf("\nempty
queue");
return;
}
for(;front<=rear;front++)
{
printf("%d\n",queue[front]);
}
front=0;
}
void
delete()
{
int i;
if((front==-1)&&(rear==-1))
{
printf("\n
empty queue");
}
for(i=0;i<=rear;i++)
{
queue[i]=queue[i+1];
}
rear--;
if(rear==-1)
front=-1;
}
Output:-
0 Comments