Priority Queue Implementation

A priority queue is an abstract data type. It is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first.

However, if elements with the same priority occur, they are served according to their order in the queue.

The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.

For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values is from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.

Algorithm

Operations associated with a priority queue in C :

isEmpty(): To check if the queue is empty
isFull(): To check whether the queue is full or not
enqueue(): add an item to the rear of the queue.
dequeue(): remove an item from the front of the queue.
Peek: get the element at front of the queue.

Implementation of Priority Queue

Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree.

But here, we will be using the structure to implement the priority queue in this tutorial.

Program using C

//PRIORITY QUEUE MENU DRIVEN
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
void CQinsert(int[], int);
int CQdelete(int []);
int CQdisplay(int []);
int front = -1, rear = -1;
int main()
{
	int ch,x,CQ[MAX],item;
	while(1)
	{
		printf("\n --- CIRCULAR QUEUE MENU --- \n 1. Insert\n 2. Delete\n 3. Display\n 4. Exit\n\n Enter your choice:- ");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1:
				printf("\nEnter the element to be inserted:- ");
				scanf("%d",&x);
				CQinsert(CQ,x);
				break;
			case 2: 
				item = CQdelete(CQ);
				if(item!=-1)
					printf("\nThe deleted item is: %d\n",item)	;
				break;
			case 3:
				CQdisplay(CQ);
				break;
			case 4: exit(0);
			default: 
				printf("\nInvalid Choice.\n");		
		}
	}
}

void CQinsert(int CQ[], int x)
{
    if(front == (rear+1)%MAX)
    {
        printf("\nOverflow - Queue is full.\n");
        exit;
    }
    else if(front == -1)
        front = rear = 0;
    else
        rear = (rear+1)%MAX;
        CQ[rear] = x;
}

int CQdelete(int CQ[])
{
    int x;
    if(front == -1)
    {
        printf("\nUnderflow - Queue is empty.\n");
        return(-1);
    }
    else
    {
        x = CQ[front];
        if(front == rear)
            front = rear = -1;
        else
            front = (front +1)%MAX;
            return x;        
    }
}

int CQdisplay(int CQ[])
{
    int i;
    if(front == -1)
        printf("\nUnderflow - Queue is empty.\n");
    else
        {
            if(front <= rear)
            {
                for(i = front; i<= rear; i++)
                printf("%d\t",CQ[i]);
        	}
            else
       		{
                for(i=front; i< MAX; i++)
                printf("%d\t",CQ[i]);
                for(i=0; i<= rear; i++)
                printf("%d\t",CQ[i]);
            }
        }
}