C++ Program to Implement Priority Queue

Write a C++ Program that demonstrates the implementation of Priority Queue.

Priority Queue in C++ is a data structure that enables insertion and removal of elements based on their priority. Elements with higher priority are always at the front of the queue. It is commonly used in scenarios where ordering elements by their priority is crucial, like task scheduling or event management systems.

Syntax of PriorityQueue in C++
In C++, a priority queue can be declared using the following syntax:

priority_queue<DataType> variablename;

Here, DataType represents the type of elements that will be stored in the priority queue. For example, if you want to create a priority queue of integers, you would use priority_queue<int> pq;.

The following operations allow for the manipulation and management of elements based on their priority in the priority queue data structure.

• push(): Adds an element to the priority queue based on its priority.
• pop(): Removes the element with the highest priority from the front of the queue.
• top(): Retrieves the element with the highest priority without removing it.
• empty(): Checks if the priority queue is empty, returning true if it is and false otherwise.
• size(): Returns the number of elements currently in the priority queue.

Here is source code of the C++ Program to demonstrate the implementation of Priority Queue. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C++ Program to Implement Priority Queue
 */
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
 
/*
 * Node Declaration
 */
struct node
{
	int priority;
	int info;
	struct node *link;
};
/*
 * Class Priority Queue
 */
class Priority_Queue
{
    private:
        node *front;
    public:
        Priority_Queue()
        {
            front = NULL;
        }
        /*
         * Insert into Priority Queue
         */
        void insert(int item, int priority)
        {
            node *tmp, *q;
            tmp = new node;
            tmp->info = item;
            tmp->priority = priority;
            if (front == NULL || priority < front->priority)
            {
                tmp->link = front;
                front = tmp;
            }
            else
            {
                q = front;
                while (q->link != NULL && q->link->priority <= priority)
                    q=q->link;
                tmp->link = q->link;
                q->link = tmp;
            }
        }
        /*
         * Delete from Priority Queue
         */
        void del()
        {
            node *tmp;
            if(front == NULL)
                cout<<"Queue Underflow\n";
            else
            {
                tmp = front;
                cout<<"Deleted item is: "<<tmp->info<<endl;
                front = front->link;
                free(tmp);
            }
        }
        /*
         * Print Priority Queue
         */
        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<<ptr->priority<<"                 "<<ptr->info<<endl;
                    ptr = ptr->link;
                }
            }
        }
};
/*
 * Main
 */
int main()
{
    int choice, item, priority;
    Priority_Queue pq; 
    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<<"Input the item value to be added in the queue : ";
            cin>>item;
            cout<<"Enter its priority : ";
            cin>>priority;
            pq.insert(item, priority);
            break;
        case 2:
            pq.del();
            break;
        case 3:
            pq.display();
            break;
        case 4:
            break;
        default :
            cout<<"Wrong choice\n";
        }
    }
    while(choice != 4);
    return 0;
}

1. The program defines a structure node to represent each element in the priority queue. It contains fields for priority, information, and a link to the next node.
2. The Priority_Queue class is defined to manage the priority queue. It has a private member front to point to the front of the queue.
3. The insert function inserts a new item into the queue based on its priority. It creates a new node, compares the priority with the front node, and inserts accordingly.
4. The del function deletes the item with the highest priority from the front of the queue and frees the memory.
5. The display function prints the contents of the queue along with their priorities.
6. The main function creates an instance of Priority_Queue and provides a menu-driven interface for the user to insert, delete, display, or quit.
7. The program loops until the user chooses to quit by entering 4.
8. Each operation is performed based on the user’s input, and the queue is modified accordingly.

Time Complexity: O(N)
The time complexity of the program is O(N) for each operation, where N is the number of elements in the priority queue.

Space Complexity: O(1)
The space complexity of the program is O(1) as it uses a fixed amount of memory for each element in the priority queue.

$ g++ priority_queue.cpp
$ a.out
 
Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 3
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 2
Enter its priority : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 1
Enter its priority : 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority       Item
1                 5
2                 4
3                 3
4                 2
5                 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Deleted item is: 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority       Item
2                 4
3                 3
4                 2
5                 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 4
 
------------------
(program exited with code: 1)
Press return to continue

1. Task Scheduling: Priority queues are used to prioritize tasks and execute them in the order of their importance.
2. Dijkstra’s Algorithm: Priority queues help find the shortest path in a graph by prioritizing vertices based on their distances.
3. Event Management: Priority queues ensure that events are processed based on their priority, such as in simulations or event-driven systems.
4. Job Scheduling: Priority queues help assign resources to jobs based on their priority.
5. Huffman Coding: Priority queues optimize data compression by assigning shorter codes to more frequent characters.

Learn more about the implementation of Priority Queue using STL and the usage of priority_queue in STL: Priority_queue in STL

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.