Priority Queue

A Priority queue is a collection of elements where each elements is assigned a priority and the order in which elements are deleted and processed is using from following rules.

• An element of higher priority is processed before any element of lower priority.

• Two elements with the same priority are processed according to the order in which they are added to the queue.

An example of a priority queue can be a timesharing system: programs of high priority are processed first, and programs with the same priority form a standard queue.

One way to represent a priority queue in memory is by means of one-way list:

• Each node in the list contains three items of information an information field INFO, a priority number PRNO and the link NEXT.

• Node A will precede Node B in the list when A has higher priority than B or when both the nodes have same priority but A was added to the list before B. This means that the order in one-way list corresponds to the order of priority queue.

Basic Operations

• insert / enqueue - add an item to the rear of the queue. 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.

• remove / dequeue - remove an item from the front of the queue. Whenever an element is to be removed from queue, queue gets the element using item count. Once an element is removed. Item count is reduced by one

An implementation of Priority Queue

We're going to implement Queue using an array. There are 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.

Listing: Following program is showing the implementation of priority Queue to Add and Delete Elements.

/* 
* C Program to Implement Priority Queue to Add and Delete Elements 
*/ 
#include <stdio.h> 
#include <stdlib.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(); 

    while (1) 
    { 
        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"); 
        } 
    } 
} 

/* 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; 
} 

Output: 

    1 - Insert an element into queue 
    2 - Delete an element from queue 
    3 - Display queue elements 
    4 - Exit 
    Enter your choice : 1 
     
    Enter value to be inserted : 20 
     
    Enter your choice : 1 
     
    Enter value to be inserted : 45 
     
    Enter your choice : 1 
     
    Enter value to be inserted : 89 
     
    Enter your choice : 3 
     89  45  20 
    Enter your choice : 1 
     
    Enter value to be inserted : 56 
     
    Enter your choice : 3 
     89  56  45  20 
    Enter your choice : 2 
     
    Enter value to delete : 45 
     
    Enter your choice : 3 
     89  56  20 
    Enter your choice : 4

Application of Queues

• Airport Simulation

• Random Numbers