Priority Queue implementation using Array in C++

Implementation of Priority Queue using Arrays in C++

Priority Queue implementation using Array in C++ is not so complicated operation. We can take two arrays one for priority and second for the data. And maintain the data and there respective priority using the index of array.There you can learn how we can implement priority queue using array and different methods to implement it.

Using ordered Array

• In ordered Array elements store in sorted for it can be in ascending order or descending order.
• So insertion takes O(n) time complexity. and deletion takes O(1) time complexity.

Using unordered Array

• In unordered Array elements store in as they insert in Queue there is no sorting.

• So Insertion takes o(1) time complexity and deletion takes o(n) time complexity.

Steps for Implementing Priority Queue in C++

Insertion

• Take data and priority from the user.
• Check if Queue is not full.
• If f=0 and rear = n-1 then print Queue is full,
• If f == r ==-1 then increment both with 1 and enqueue data from the rear.
• Else if there is some elements in array we will compare the priority of entered element with the priority of elements in Queue.
• When we finds out the position of element which is smaller then entered priority then we insert the entered element before it.

Deletion

• If front == -1 then print underflow condition.
• Else print the element from the front.
• If front == rear then initialize front = rear =-1
• Else increment front by 1.

Print

• Traverse a Queue with the help of loop from front to rear and print the data and priority of Queue.

C++ Program to Implement Max Priority Queue (using Ordered Array)

```#include<iostream>
#define N 20
using namespace std;
int Q[N],Pr[N];
int r = -1,f = -1;
void enqueue(int data,int p)//Enqueue function to insert data and its priority in queue
{
int i;
if((f==0)&&(r==N-1)) //Check if Queue is full
cout<<"Queue is full";
else
{
if(f==-1)//if Queue is empty
{
f = r = 0;
Q[r] = data;
Pr[r] = p;

}
else if(r == N-1)//if there there is some elemets in Queue
{
for(i=f;i<=r;i++) {
Q[i-f] = Q[i];
Pr[i-f] = Pr[i];
r = r-f;
f = 0;
for(i = r;i>f;i--)
{
if(p>Pr[i])
{
Q[i+1] = Q[i];
Pr[i+1] = Pr[i];
}
else
break;
Q[i+1] = data;
Pr[i+1] = p;
r++;
}
}
}
else
{
for(i = r;i>=f;i--)
{
if(p>Pr[i])
{
Q[i+1] = Q[i];
Pr[i+1] = Pr[i];
}
else
break;
}
Q[i+1] = data;
Pr[i+1] = p;
r++;
}
}

}
void print() //print the data of Queue
{
int i;
for(i=f;i<=r;i++)
{
cout<<"Element ="<<Q[i]<<"Priority = "<<Pr[i]<<endl;
}
}
int dequeue() //remove the data from front
{
if(f == -1)
{
cout<<"Queue is Empty";
}
else
{
cout<<"deleted Element ="<<Q[f]<<endl;
cout<<"Its Priority = "<<Pr[f]<<endl;
if(f==r)
f = r = -1;
else
f++;
}
}
int main()
{
int opt,n,i,data,p;
do{
cout<<"1 for Insert the Data in Queue\n2 for show the Data in Queue \n3 for Delete the data from the Queue\n0 for Exit"<<endl;
cin>>opt;
switch(opt){
case 1:
cout<<"Enter the number of data"<<endl;
cin>>n;
cout<<"Enter your data and Priority of data"<<endl;
i=0;
while(i<n){
cin>>data;
cin>>p;
enqueue(data,p);
i++;
}
break;
case 2:
print();
break;
case 3:
dequeue();
break;
case 0:
break;
default:
cout<<"Incorrect Choice"<<endl;

}
}while(opt!=0);
return 0;
}```
`Enter Your Choice:-1 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit1Enter the number of data 5Enter your data and Priority of data 34 8438 6345 6177 5583 221 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit3deleted Element = 34     Its Priority = 841 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit2Element = 38    Priority = 63Element = 45    Priority = 61Element = 77    Priority = 55Element = 83    Priority = 221 for Insert the Data in Queue2 for show the Data in Queue3 for Delete the data from the Queue0 for Exit`