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.

Priority Queue in using array C++

Priority Queue Implementation

 

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.
Priority queue using array in C ++

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;
	cout<<"Enter Your Choice:-"<<endl;
	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 Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit
1

Enter the number of data 5

Enter your data and Priority of data
34 84
38 63
45 61
77 55
83 22

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit
3
deleted Element = 34 Its Priority = 84

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit
2

Element = 38 Priority = 63
Element = 45 Priority = 61
Element = 77 Priority = 55
Element = 83 Priority = 22

1 for Insert the Data in Queue
2 for show the Data in Queue
3 for Delete the data from the Queue
0 for Exit