Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Priority Queue using Arrays in C Programming

Implementation of Priority Queue using Arrays in C

Priority Queue implementation using array is the one of the basic method to implement Queue.In Priority Queue data who has highest priority remove from the Queue first and second highest priority element after it and so on.In priority Queue each element has its own priority.If priority is same for two elements then data remove on the basis of first come first serve.

Priority Queue

Types of Priority Queue:

  • Min Priority Queue: In min priority Queue minimum number of value gets the highest priority and lowest number of element gets the highest priority.
  • Max Priority Queue: Max priority Queue is the opposite of min priority Queue in it maximum number value gets the highest priority and minimum number of value gets the minimum priority.

Priority Queue Implementation

Priority Queue can be impleted in two ways:

  • Using ordered Array: In ordered array insertion or enqueue operation takes O(n) time complexity because it enters elements in sorted order in queue. And deletion takes O(1) time complexity. 
  • Using unordered Array:In unordered array deletion takes O(n) time complexity because it search for the element in Queue for the deletion and enqueue takes o(1) time complexity.

Steps for Implementing Priority Queue in C

Insertion

  • Ask the data and its priority from the user.
  • If front is equal to 0 and rear is equal to n-1 then Queue is full.
  • Else if front is equal to the -1 them queue is empty so we have initialize front and rear with 0.
  • Insert the data entered by user in Queue using rear.
  • If rear is equal to n-1 and front is not equal to 0 then there is empty space in queue before the front for using that space we will shift the elements of the queue with the help of front and rear.
  • Insert the data in the queue before at the position where given priority is greater then priority of the element in queue.

Deletion

  • Remove the element and the priority from the front of the queue.
  • Increase front with 1.

 Print

  • Using loop take the starting point from the front of the queue and ending point from the rear of the queue and print the data.
Priority queue using array in C

Algorithm to implement Priority Queue using Array

  • Enqueue()

    1. IF((Front == 0)&&(Rear == N-1))
    2. PRINT “Overflow Condition”
    3. Else
    4. IF(Front == -1)
    5. Front = Rear =0
    6. Queue[Rear] = Data
    7. Priority[Rear] = Priority
    8. ELSE IF(Rear ==N-1)
    9. FOR i=Front;i<=Rear;i++)
    10. FOR(i=Front;i<=Rear;i++) 
    11. Q[i-Front] =Q[i]
    12. Pr[i-Front] = Pr[i]
    13. Rear = Rear-Front
    14. Front = 0
    15. FOR(i = r;i>f;i–)
    16. IF(p>Pr[i])
    17. Q[i+1] = Q[i] Pr[i+1] = Pr[i]
    18. ELSE 
    19. Q[i+1] = data Pr[i+1] = p
    20. Rear++
  • Dequeue()

    1. IF(Front == -1)
    2. PRINT “Queue Under flow condition” 
    3. ELSE
    4. PRINT”Q[f],Pr[f]”
    5. IF(Front==Rear)
    6. Front = Rear = -1
    7. ELSE
    8. FRONT++
  • Print()

    1. FOR(i=Front;i<=Rear;i++)
    2. PRINT(Q[i],Pr[i])

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

#include<stdio.h>
#define N 20
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
		printf("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++)
	{
		printf("\nElement = %d\tPriority = %d",Q[i],Pr[i]);
	}
}
int dequeue() //remove the data from front
{
	if(f == -1)
	{
		printf("Queue is Empty");
	}	
	else
	{
		printf("deleted Element = %d\t Its Priority = %d",Q[f],Pr[f]);
		if(f==r)
			f = r = -1;
		else
			f++;
	}
}
int main()
{
	int opt,n,i,data,p;
	printf("Enter Your Choice:-");
	do{
		printf("\n\n1 for Insert the Data in Queue\n2 for show the Data in Queue \n3 for Delete the data from the Queue\n0 for Exit");
		scanf("%d",&opt);
		switch(opt){
			case 1:
				printf("\nEnter the number of data");
				scanf("%d",&n);
				printf("\nEnter your data and Priority of data");
				i=0;
				while(i<n){
					scanf("%d %d",&data,&p);
					enqueue(data,p);
					i++;
				}
				break;
			case 2:
				print();
				break;
			case 3:
				 dequeue();
				break;
			case 0:
				break;
			default:
				printf("\nIncorrect Choice");

		}
	}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

2 comments on “Priority Queue using Arrays in C Programming”