Priority Queue

In this element inserted and deleted based on the priority. The elements in priority queue have some priority. The priority of the element is used to determine the order in which the elements will be processed.

The basic examples of Priority Queue are -

• Routing
• Operating System Scheduler
• Dijkstra's Shortest Path Algorithm
• Huffman Coding

These are the rules to process elements in a priority queue.

• The element with the highest priority is processed first.
• The two elements with equal priority is processed based on First Come First Serve(FCFS) basis.

The priority of the elements is set based on several factors. This is basically used in the operating system to execute the highest priority process first. If this is set on the CPU time, then the element with lowest execution time is executed first. Suppose there are two processes in a queue, one has 5ns execution time and other has 10ns execution time, then the process having 5ns execute first.

Priority Queue Implementation

These are two ways to implement the priority queues.

• Sorted List (Array or Linked List)
• Unsorted List (Array or Linked List)
• Heap

Sorted List

The sorted list takes 0(n) time to insert an element to the list and 0(1) time to delete an element from the list.

Unsorted List

The unsorted list takes 0(1) time to insert an element to the list and 0(n) time to delete an element from the list.

Priority Queue Program in C

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 10

void create_queue(); 
void insert_element(int); 
void delete_element(int); 
void check_priority(int); 
void display_priorityqueue(); 

int pqueue[MAX]; 
int front, rear; 

void main() 
{ 
    int n, che;  
    printf("\nEnter 1 to insert element by priority "); 
    printf("\nEnter 2 to delete element by priority "); 
    printf("\nEnter 3 to display priority queue "); 
    printf("\nEnter 4 to exit");  
    create_queue();  
    while (1) 
    { 
        printf("\nEnter your choice : ");    
        scanf("%d", &che);   
        switch(che) 
        { 
        case 1: 
            printf("\nEnter element to insert : "); 
            scanf("%d",&n); 
            insert_element(n); 
            break; 
        case 2: 
            printf("\nEnter element to delete : "); 
            scanf("%d",&n); 
            delete_element(n); 
            break; 
        case 3: 
            display_priorityqueue(); 
            break; 
        case 4: 
            exit(0); 
        default: 
            printf("\n Please enter valid choice"); 
        } 
    } 
}  
void create_queue() 
{ 
    front = rear = -1; 
}  
void insert_element(int data) 
{ 
    if (rear >= MAX - 1) 
    { 
        printf("\nQUEUE OVERFLOW"); 
        return; 
    } 
    if ((front == -1) && (rear == -1)) 
    { 
        front++; 
        rear++; 
        pqueue[rear] = data; 
        return; 
    }    
    else 
        check_priority(data); 
    rear++; 
}  
void check_priority(int data) 
{ 
    int i,j;  
    for (i = 0; i <= rear; i++) 
    { 
        if (data >= pqueue[i]) 
        { 
            for (j = rear + 1; j > i; j--) 
            { 
                pqueue[j] = pqueue[j - 1]; 
            } 
            pqueue[i] = data; 
            return; 
        } 
    } 
    pqueue[i] = data; 
}  
void delete_element(int data)  
{ 
    int i;  
    if ((front==-1) && (rear==-1)) 
    { 
        printf("\nEmpty Queue"); 
        return; 
    }  
    for (i = 0; i <= rear; i++) 
    { 
        if (data == pqueue[i]) 
        { 
            for (; i < rear; i++) 
            { 
                pqueue[i] = pqueue[i + 1]; 
            } 
            pqueue[i] = -99; 
            rear--; 
            if (rear == -1) 
               front = -1; 
            return; 
        } 
    } 
    printf("\n%d element not found in queue", data); 
} 
void display_priorityqueue() 
{ 
    if ((front == -1) && (rear == -1)) 
    { 
        printf("\nEmpty Queue "); 
        return; 
    }  
    for (; front <= rear; front++) 
    { 
        printf(" %d ", pqueue[front]); 
    } 
     front = 0; 
} 

Output of the above program-

Enter 1 to insert element by priority 
Enter 2 to delete element by priority 
Enter 3 to display priority queue 
Enter 4 to exit
Enter your choice : 1

Enter element to insert : 34

Enter your choice : 1

Enter element to insert : 43

Enter your choice : 1

Enter element to insert : 67

Enter your choice : 3
 67  43  34 
Enter your choice : 2

Enter element to delete : 43

Enter your choice : 3
 67  34 
Enter your choice :