What is Priority Queue?

A priority queue is a sort of queue that stores items in a queue based on their priority. As a result, it does not support the FIFO (First In, First Out) structure.


Operations :

InsertWithPriority: Insert a queue item with the corresponding priority.

GetNext: remove the element with the greatest priority from the queue and return it. PopElement() and GetMaximum are other names for it.

PeekAtNext (optional): Retrieve the highest-priority item without deleting it.


Implementation with all above queue operations :


#include <iostream>
using namespace std;

typedef struct node
{
    int priority;
    int info;
    struct node *link;
} NODE;
NODE *front = NULL;

// insert method
void insert(int data, int priority)
{
    NODE *temp, *q;

    temp = (NODE *)malloc(sizeof(NODE));
    temp->info = data;
    temp->priority = priority;
    // condition to check whether the first element is empty or the element to be inserted has more priority than the first element
    if (front == NULL || priority < front->priority)
    {
        temp->link = front;
        front = temp;
    }
    else
    {
        q = front;
        while (q->link != NULL && q->link->priority <= priority)
            q = q->link;
        temp->link = q->link;
        q->link = temp;
    }
}

// delete method

void del()
{
    NODE *temp;
    // condition to check whether the Queue is empty or not
    if (front == NULL)
        cout << "Queue Underflow\n";
    else
    {
        temp = front;
        cout << "Deleted item is %d\n", temp->info;
        front = front->link;
        free(temp);
    }
}
// display method
void display()
{
    NODE *ptr;
    ptr = front;
    if (front == NULL)
        cout << "Queue is empty\n";
    else
    {
        cout << "Queue is :\n";
        cout << "Priority     Item\n";
        while (ptr != NULL)
        {
            // cout << "priority : " << ptr->priority << "\ninfo : " << ptr->info << endl;
            cout << "   " << ptr->priority << "         " << ptr->info << endl;
            ptr = ptr->link;
        }
    }
}
/*End of display*/

// main method
int main()
{
    int choice, data, priority;
    do
    {
        cout << "1.Insert\n";
        cout << "2.Delete\n";
        cout << "3.Display\n";
        cout << "4.Quit\n";
        cout << "Enter your choice : ";

        cin >> choice;

        switch (choice)
        {
        case 1:
            cout << "Enter the data  : ";
            cin >> data;
            cout << "Enter its priority : ";
            cin >> priority;
            insert(data, priority);
            break;
        case 2:
            del();
            break;
        case 3:
            display();
            break;
        case 4:
            break;
        default:
            cout << "Wrong choice\n";
        }
    } while (choice != 4);

    return 0;
}

Output:

 1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Enter the data  : 2
Enter its priority : 30
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Enter the data  : 50
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Enter the data  : 60
Enter its priority : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority     Item
   3       50
   4       60
   30       2