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


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

Queue implementation in STL

QUEUES:

Queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

queues are implemented as containers 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 pushed into the “back” of the specific container and popped from its “front”.

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

  • empty
  • size
  • front
  • back
  • push_back
  • pop_front

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

C++ Program for Queue implementation in STL

#include <iostream>
#include <queue>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
    queue<int> q;
    int choice, item;
    while (1)
    {
        cout<<"n---------------------"<<endl;
        cout<<"Queue Implementation in Stl"<<endl;
        cout<<"n---------------------"<<endl;
        cout<<"1.Insert Element into the Queue"<<endl;
        cout<<"2.Delete Element from the Queue"<<endl;
    cout<<"3.Size of the Queue"<<endl;
        cout<<"4.Front Element of the Queue"<<endl;
        cout<<"5.Last Element of the Queue"<<endl;
        cout<<"6.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter value to be inserted: ";
            cin>>item;
            q.push(item);
            break;
        case 2:
            item = q.front();
            q.pop();
            cout<<"Element "<<item<<" Deleted"<<endl;
            break;
        case 3:
        cout<<"Size of the Queue: ";
        cout<<q.size()<<endl;
            break;
        case 4:
            cout<<"Front Element of the Queue: ";
        cout<<q.front()<<endl;
            break;
        case 5:
            cout<<"Back Element of the Queue: ";
            cout<<q.back()<<endl;
            break;
        case 6:
            exit(1);
        break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

Sample Output:

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

---------------------
1.Insert Element into the Queue
2.Delete Element from the Queue
3.Size of the Queue
4.Front Element of the Queue
5.Last Element of the Queue
6.Exit
Enter your Choice: 2
Element 9 Deleted

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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

---------------------
Queue Implementation in Stl

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


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

 

Set implementation in C++ STL

Set Sets are containers that store unique elements following a specific order. In a set, the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. The value of the elements in a set cannot be modified once in the container (the elements … Read more

Map implementation in STL

Map Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key … Read more

Vector implementation in STL

Vector:

Vectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

C++ Program for Vector implementation in STL:

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
    vector<int> ss;
    vector<int>::iterator it;
    int choice, item;
    while (1)
    {
        cout<<"n---------------------"<<endl;
        cout<<"Vector Implementation in Stl"<<endl;
        cout<<"n---------------------"<<endl;
        cout<<"1.Insert Element into the Vector"<<endl;
        cout<<"2.Delete Last Element of the Vector"<<endl;
        cout<<"3.Size of the Vector"<<endl;
        cout<<"4.Display by Index"<<endl;
        cout<<"5.Dislplay by Iterator"<<endl;
        cout<<"6.Clear the Vector"<<endl;
        cout<<"7.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter value to be inserted: ";
            cin>>item;
            ss.push_back(item);
            break;
        case 2:
            cout<<"Delete Last Element Inserted:"<<endl;
            ss.pop_back();
            break;
        case 3:
            cout<<"Size of Vector: ";
            cout<<ss.size()<<endl;
            break;
        case 4:
            cout<<"Displaying Vector by Index: ";
            for (int i = 0; i < ss.size(); i++)
            {
                cout<<ss[i]<<" ";
            }
            cout<<endl;
            break;
        case 5:
            cout<<"Displaying Vector by Iterator: ";
            for (it = ss.begin(); it != ss.end(); it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
            break;
        case 6:
            ss.clear();
            cout<<"Vector Cleared"<<endl;
            break;
        case 7:
            exit(1);
            break;
        default:
            cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

Sample Output:

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 4

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 6

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 3

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 8

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 9

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 1
Enter value to be inserted: 2

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 3
Size of Vector: 6

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 4
Displaying Vector by Index: 4 6 3 8 9 2

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 2
Delete Last Element Inserted:

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 3
Size of Vector: 5

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 5
Displaying Vector by Iterator: 4 6 3 8 9

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 4
Displaying Vector by Index: 4 6 3 8 9

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 6
Vector Cleared

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 3
Size of Vector: 0

---------------------
Vector Implementation in Stl

---------------------
1.Insert Element into the Vector
2.Delete Last Element of the Vector
3.Size of the Vector
4.Display by Index
5.Dislplay by Iterator
6.Clear the Vector
7.Exit
Enter your Choice: 7


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

 

C++ Program to Implement Floyd Warshall Algorithm

Floyd Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves.

Pseudo code:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] ← dist[i][k] + dist[k][j]
         end if

 

Example:

Floyd Warshall algorithm

 

Prior to the first iteration of the outer loop, labeled k=0 above, the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found. Finally, at k=4, all shortest paths are found.

C++ program to implement Floyd Warshall Algorithm:

#include <iostream>
using namespace std;

void floyds(int b[][7])
{
    int i, j, k;
    for (k = 0; k < 7; k++)
    {
        for (i = 0; i < 7; i++)
        {
            for (j = 0; j < 7; j++)
            {
                if ((b[i][k] * b[k][j] != 0) && (i != j))
                {
                    if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
                    {
                        b[i][j] = b[i][k] + b[k][j];
                    }
                }
            }
        }
    }
    for (i = 0; i < 7; i++)
    {
        cout<<"nMinimum Cost With Respect to Node:"<<i<<endl;
        for (j = 0; j < 7; j++)
        {
            cout<<b[i][j]<<"t";
        }
    }
}
int main()
{
        int b[7][7];
        cout<<"ENTER VALUES OF ADJACENCY MATRIXnn";
        for (int i = 0; i < 7; i++)
        {
                cout<<"enter values for "<<(i+1)<<" row"<<endl;
                for (int j = 0; j < 7; j++)
                cin>>b[i][j];
        }
        floyds(b);
        return 0;
}

OUTPUT:

ENTER VALUES OF ADJACENCY MATRIX

enter values for 1 row
0
3
6
0
0
0
0
enter values for 2 row
3
0
2
4
0
0
0
enter values for 3 row
6
2
0
1
4
2
0
enter values for 4 row
0
4
1
0
2
0
4
enter values for 5 row
0
0
4
2
0
2
1
enter values for 6 row
0
0
2
0
2
0
1
enter values for 7 row
0
0
0
4
1
1
0

Minimum Cost With Respect to Node:0
0       3       5       6       8       7       8
Minimum Cost With Respect to Node:1
3       0       2       3       5       4       5
Minimum Cost With Respect to Node:2
5       2       0       1       3       2       3
Minimum Cost With Respect to Node:3
6       3       1       0       2       3       3
Minimum Cost With Respect to Node:4
8       5       3       2       0       2       1
Minimum Cost With Respect to Node:5
7       4       2       3       2       0       1
Minimum Cost With Respect to Node:6
8       5       3       3       1       1       0