Software & Finance - Monthly Magazine Online

Volume 2 - Issue 6

June 2012

Implementing Priority Queue


 

Queue elements are following FIFO structure. But priority queue will check for the priority and then place the element in the right place based on priority.

 

In another words, if you have a priority_queue of integers, then if you iterate through all elements, then it will be in sorted order by Descending.

 

If you have an object collection in priority_queue, then you are responsible for comparing the objects. It can be done on the same class. Refer to the following function in the sample code:

bool operator() (const CPriorityData &lhs, const CPriorityData &rhs)

 

#include < iostream >
#include < deque >
#include < queue >
#include < stack >
#include < map >
#include < string >

struct CPriorityData 
{
   std::string  m_type;
   int m_rank;

public:

   CPriorityData() : m_type(""), m_rank(0)
   {
   }

   CPriorityData(std::string type, int rank)
      : m_type(type), m_rank(rank)
   {

   }

   bool operator() (const CPriorityData &lhs, const CPriorityData &rhs)
   {
      if(lhs.m_rank < rhs.m_rank)
         return true;
      return false;
   }
};


void main()
{
   std::cout << "Queue Collection: \n";
   std::queue< std::string > myCollection;
   myCollection.push("David");
   myCollection.push("Erin");
   myCollection.push("John");

   while(myCollection.size())
   {
      std::string type = myCollection.front();
      std::cout << "\n" << type.c_str();
      myCollection.pop();
   }

   std::cout << "\n\nPriority Queue Collection: \n";
   std::priority_queue< CPriorityData, std::vector < CPriorityData >, CPriorityData > myPriorityCollection;
   myPriorityCollection.push(CPriorityData("David", 1));
   myPriorityCollection.push(CPriorityData("Erin", 2));
   myPriorityCollection.push(CPriorityData("John", 3));

   while(myPriorityCollection.size())
   {
      CPriorityData type = myPriorityCollection.top();
      std::cout << "\n" << type.m_type.c_str();
      std::cout << "\tRank:" << type.m_rank;
      myPriorityCollection.pop();
   }
   std::cout << "\n\n";

   std::cout << "\n\nPriority Queue of Integer Values";
   std::priority_queue < int > myInts;
   myInts.push(10);
   myInts.push(30);
   myInts.push(40);
   myInts.push(20);
   while(myInts.size())
   {
      std::cout  << "\n" << myInts.top();
      myInts.pop();
   }

   std::cout << "\n\n";

   return;
}

    

Sample Output

 

Queue Collection:

David
Erin
John

Priority Queue Collection:

John Rank:3
Erin Rank:2
David Rank:1

 

Priority Queue of Integer Values
40
30
20
10

Press any key to continue . . .