Priority Queue

Priority queue:- It is a special type of queue which stores group of elements. Each element has a priority number associated with it. Priority queue is an ADT (Abstract Data Type) which is like a regular queue or data structure but it will provide services on the basis of priority of an element.

यह एक विशेष प्रकार का क्यू होता है जो एलिमेंट्स का समूह रखता है। प्रत्येक एलिमेंट से एक प्रायोरिटी नंबर संलग्न होता है। प्रायोरिटी क्यू एक ADT है जो एक सामान्य क्यू या डाटा स्ट्रक्चर के समान है परंतु यह एलिमेंट की प्रायोरिटी (प्राथमिकता) के आधार पर सुविधा प्रदान करता है।

Rules of Priority Queue-

प्रायोरिटी क्यू के नियम-

1. Element which has higher priority will be inserted and deleted before other elements which has lower priority.

वह एलिमेंट जिसकी प्रायोरिटी अधिक होती है अन्य कम प्रायोरिटी एलिमेंट्स की तुलना में पहले इन्सर्ट एवं डिलीट किया जावेगा।

2. If two or more element has same priority then we follow FCFS (first come first serve) approach in which elements are deleted in order of their insertion in queue.

यदि दो या अधिक एलिमेंट की प्रायोरिटी एकसमान है तब हम FCFS(फर्स्ट कम फर्स्ट सर्व) युक्ति का प्रयोग करते है अर्थात जिस क्रम में एलिमेंट क्यू में इन्सर्ट होता है उसी क्रम में डिलीट होगा।

Operations performed in Priority Queue - 

प्रायोरिटी क्यू पर किये जाने वाले आपरेशन निम्न है-

1. Insertion with priority (इंसर्शन विथ प्रायोरिटी):- add an element to the queue with an associated priority.

एक एलिमेंट को उसकी प्रायोरिटी के अनुसार क्यू में जोड़ना।

2. Delete highest priority element(डिलीट हाईएस्ट प्रायोरिटी एलिमेंट):- remove the element from queue that has the highest priority and written it.

सबसे उच्च प्रायोरिटी एलिमेंट को क्यू से निकलना एवं लिखना।

Example:- In computer system, a priority queue is maintained by long term and short term scheduler which is also known as process queue. Here each process will execute on the basis of its priority like first of all interrupt then system process then resource request and at the end normal user process will be executed.

उदाहरण:- कंप्यूटर साइंस में लांग टर्म एवं शार्ट टर्म शेड्यूलर द्वारा प्रायोरिटी क्यू तैयार किया जाता है। इसे प्रोसेस क्यू कहा जाता है, जिसके आधार पर प्रोसेस को एक्सीक्यूट किया जाता है। अर्थात सर्वप्रथम इनट्ररप्ट इसके पश्चात सिस्टम प्रोसेस उसके बाद रिसोर्स रिक्वेस्ट एवं अंत मे सामान्य यूजर प्रोसेस को रन किया जता है।

Priority queue is mainly used in binary search tree, heap data structure, bucket queue, Dijkstra's algorithm, Huffman coding, best first search algorithm and prim's algorithm for minimum spanning tree etc.

प्रायोरिटी क्यू का प्रयोग मुख्यतः बाइनरी सर्च ट्री , हीप डेटा स्ट्रक्चर, बकेट क्यू , डिजक्सट्रा अल्गोरिथम , हुफमन कोडिंग, ब्रेड्थ फर्स्ट सर्च अल्गोरिथम एवं मिनिमम स्पांनिंग ट्री की प्राइम अल्गोरिथम इत्यादि में किया जाता है।

C Program to implement Priority Queue:-

#include <stdio.h>

#include <stdlib.h>

#define MAX 5

int pri_que[MAX];

int front=-1, rear=-1;

void insert_by_priority(int item){

    if (rear >= MAX - 1)

    {

        printf("overflow condition\n");

        getch();     

        return;

    }

    if ((front == -1) && (rear == -1))

    {

        front++;

        rear++;

        pri_que[rear] = item;

        return;

    } 

    else

        checkpriority(item);

    rear++;

}

/* Function to check priority of an item */

void checkpriority(int item)

{

    int i,j;

    for (i = 0; i <= rear; i++)

    {

        if (item >= pri_que[i])

        {

            for (j = rear + 1; j > i; j--)

            {

                pri_que[j] = pri_que[j - 1];

            }

            pri_que[i] = item;

            return;

        }

    }

    pri_que[i] = item;

}

void delete_by_priority(int item)

{

    int i;

    if ((front==-1) && (rear==-1))

    {

        printf("\nQueue is empty no elements to delete");

        return;

    }

    for (i = 0; i <= rear; i++)

    {

        if (item == 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", item);

}

void display_pqueue()

{

    if ((front == -1) && (rear == -1))

    {

        printf("\nQueue is empty");

        return;

    }

    for (; front <= rear; front++)

    {

        printf(" %d ", pri_que[front]);

    }

    front = 0;

}

void main()

{

    int n, ch;

    printf("\nPriority Queue Operations:- \n 1. Insert an element into queue\n2. Delete an element from queue\n3. Display queue elements\n4. Exit");

    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("\nWrong Choice, Try Again !!");

        }

    }

}