Priority Queue

Priority Queue is more specialized data structure than Queue. Like ordinary queue, priority queue has same method but with a major difference. In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we’re assigned priority to item based on its key value. Lower the value, higher the priority. Following are the principal methods of a Priority Queue.

Basic Operations :-

• insert / enqueue − add an item to the rear of the queue.
• remove / dequeue − remove an item from the front of the queue.

Priority Queue Representation :-

We’re going to implement Queue using array in this article. There is few more operations supported by queue which are following.

• Peek − get the element at front of the queue.
• isFull − check if queue is full.
• isEmpty − check if queue is empty.

Insert / Enqueue Operation :-

Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we’re assuming that data with high value has low priority.

** Insert by priority function **
/* Function to insert value into priority queue */
	void insert_by_priority(int data)
	{
	    if (rear >= MAX - 1)
	    {
	        printf("\nQueue overflow no more elements can be inserted");
	        return;
	    }
	    if ((front == -1) && (rear == -1))
	    {
	        front++;
	        rear++;
	        pri_que[rear] = data;
	        return;
	    }    
	    else
	        check(data);
	    rear++;
}

Remove / Dequeue Operation :-

Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.

** Delete an by priority function **
/* Function to delete an element from queue */
	void delete_by_priority(int data)
	{
	    int i;	 
	    if ((front==-1) && (rear==-1))
	    {
 	       printf("\nQueue is empty no elements to delete");
 	       return;
 	    }
	    for (i = 0; i <= rear; i++)
	    {
	        if (data == pri_que[i])
	        {
	            for (; i < rear; i++)
	            {
	                pri_que[i] = pri_que[i + 1];
        	    }
	        pri_que[i] = -99;
        	rear--;
 
 	       if (rear == -1) 
 	           front = -1;
     	  	 	return;
        	}
    	}
    	printf("\n%d not found in queue to delete", data);
}

				*******************
				Programming Example
				*******************

1. Write a program to implement a priority queue.

#include<stdio.h>
#include<conio.h>
 
#define MAX 5
 
void insert_by_priority(int);
void delete_by_priority(int);
void create();
void check(int);
void display_pqueue();
 
int pri_que[MAX];
int front, rear;
 
void main()
{
    int n, ch;
 
    printf("\n1 - Insert an element into queue");
    printf("\n2 - Delete an element from queue");
    printf("\n3 - Display queue elements");
    printf("\n4 - Exit");
 
    create();
 
    do
    {
        printf("\nEnter your choice : ");    
        scanf("%d", &ch);
 
        switch (ch)
        {
        case 1: 
            printf("\nEnter value to be inserted : ");
            scanf("%d",&n);
            insert_by_priority(n);
            break;
        case 2:
            printf("\nEnter value to delete : ");
            scanf("%d",&n);
            delete_by_priority(n);
            break;
        case 3: 
            display_pqueue();
            break;
        case 4: 
            exit(0);
        default: 
            printf("\nChoice is incorrect, Enter a correct choice");
        }
    }while!=(4);
}
 
/* Function to create an empty priority queue */
void create()
{
    front = rear = -1;
}
 
/* Function to insert value into priority queue */
void insert_by_priority(int data)
{
    if (rear >= MAX - 1)
    {
        printf("\nQueue overflow no more elements can be inserted");
        return;
    }
    if ((front == -1) && (rear == -1))
    {
        front++;
        rear++;
        pri_que[rear] = data;
        return;
    }    
    else
        check(data);
    rear++;
}
 
/* Function to check priority and place element */
void check(int data)
{
    int i,j;
 
    for (i = 0; i <= rear; i++)
    {
        if (data >= pri_que[i])
        {
            for (j = rear + 1; j > i; j--)
            {
                pri_que[j] = pri_que[j - 1];
            }
            pri_que[i] = data;
            return;
        }
    }
    pri_que[i] = data;
}
 
/* Function to delete an element from queue */
void delete_by_priority(int data)
{
    int i;
 
    if ((front==-1) && (rear==-1))
    {
        printf("\nQueue is empty no elements to delete");
        return;
    }
 
    for (i = 0; i <= rear; i++)
    {
        if (data == pri_que[i])
        {
            for (; i < rear; i++)
            {
                pri_que[i] = pri_que[i + 1];
            }
 
        pri_que[i] = -99;
        rear--;
 
        if (rear == -1) 
            front = -1;
        return;
        }
    }
    printf("\n%d not found in queue to delete", data);
}
 
/* Function to display queue elements */
void display_pqueue()
{
    if ((front == -1) && (rear == -1))
    {
        printf("\nQueue is empty");
        return;
    }
 
    for (; front <= rear; front++)
    {
        printf(" %d ", pri_que[front]);
    }
 
    front = 0;
}