Priority Queue in STL implementation in C++

In this post first we will understand what a Priority Queue is and then we will write a program in C++ to implement Priority Queue in STL. Let’s understand what a Priority Queue is.

Priority queue:

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the “back” of the specific container, which is known as the top of the priority queue.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following operations:

  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()

C++ program to implement Priority Queue in STL:

#include <iostream>
#include <queue>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
    priority_queue<int> pq;
    int choice, item;
    while (1)
    {
        cout<<"\n---------------------"<<endl;
        cout<<"Priority Queue in Stl"<<endl;
        cout<<"\n---------------------"<<endl;
        cout<<"1.Insert Element into the Priority Queue"<<endl;
        cout<<"2.Delete Element from the Priority Queue"<<endl;
        cout<<"3.Size of the Priority Queue"<<endl;
        cout<<"4.Top Element of the Priority Queue"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter value to be inserted: ";
            cin>>item;
            pq.push(item);
            break;
        case 2:
            item = pq.top();
            if (!pq.empty())
            {
                pq.pop();
                cout<<"Element "<<item<<" Deleted"<<endl;
            }
            else
            {
                cout<<"Priority Queue is Empty"<<endl;
            }
            break;
        case 3:
            cout<<"Size of the Queue: ";
        cout<<pq.size()<<endl;
            break;
        case 4:
            cout<<"Top Element of the Queue: ";
            cout<<pq.top()<<endl;
            break;
        case 5:
            exit(1);
        break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

 

Sample Output:
---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 5

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 3

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 7

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 4

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 2

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 1
Enter value to be inserted: 8

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 3
Size of the Queue: 6

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 4
Top Element of the Queue: 8

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 2
Element 8 Deleted

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 3
Size of the Queue: 5

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 4
Top Element of the Queue: 7

---------------------
Priority Queue in Stl

---------------------
1.Insert Element into the Priority Queue
2.Delete Element from the Priority Queue
3.Size of the Priority Queue
4.Top Element of the Priority Queue
5.Exit
Enter your Choice: 5


------------------

Leave a Comment