Link to home
Start Free TrialLog in
Avatar of carbuff1976
carbuff1976

asked on

How to implement a priority queue header in C++ using STL?

Here is my vpqueue.h that i need to implement for my project. I think i have most of it but I am stuck on what i am missing since the program goes and only writes the same itme out to the screen and i know i must be missing something in the header file that is messing the program up.


// here was the programming exercise i was tasked with///
------------------------------------------------------------
#include <vector>
#include "d_except.h"

using namespace std;

class vpriority_queue
{                      
      public:
            vpriority_queue();
                  // default constructor. create an empty priority queue
     
            int size() const;
                  // return the size of the priority queue
            bool empty() const;
                  // is the priority queue empty?

            void push(const T& item);
                  // insert item into the priority queue
                  // Postcondition: the priority queue has one more  element
            void pop();
                  // remove the highest priority (maximum) item from the priority queue.
                  // Precondition: the priority queue is not empty.
                  // if it is empty, the function throws the underflowError exception

            T& top();
                  // return the highest priority (maximum) item in the priority queue
                  // Precondition: the priority queue is not empty.
                  // if it is empty , the function throws the underflowError excpetion

            const T& top() const;
                  // constant version

      private:
            vector<T> pqVector;
                  // pqVector holds the priority queue elements
                                                // vector that implements the priority queue


            
            int findMaxIndex() const;
            // find the index of the maximum value in pqVector
      
            int maxIndex;
                                // index of the maximum value
                  
            bool recomputeMaxIndex;
                                // do we need to compute the inmdex of the maximum element?
};

//Now this is where i tried to implement all the parts of the header file//
--------------------------------------------------------------------------------------

// constructor. create empty priority queue

vpriority_queue<T>::vpriority_queue()
{
     recomputeMaxIndex=true;
}


// return the size of the priority queue
template <typename T>
int vpriority_queue<T>::size() const
{
   return pqVector.size();
}

// return true if the priority queue is empty and false
// otherwise
template <typename T>
bool vpriority_queue<T>::empty() const
{
   return pqVector.empty();
}

// insert a new item in the priority queue
template <typename T>
void vpriority_queue<T>::push(const T& item)
{
      // insert the item at the end of the vector
      pqVector.push_back(item);

      recomputeMaxIndex = true;
}

// remove the element of highest priority,
template <typename T>
void vpriority_queue<T,Compare>::pop()
{
      // check for an empty priority queue
      if (pqVector.empty())
            throw underflowError("vpriority_queue pop(): empty list");

      // delele element from back of pqVector
      pqVector.pop_back();
}

template <typename T>
T& vpriority_queue<T>::top()
{
   // check for empty
   if (pqVector.empty())
            throw underflowError("vpriority_queue top(): empty list");

      // return
      return pqVector[maxIndex];
}

template <typename T>
const T& vpriority_queue<T>::top() const
{
   // check for an empty heap
   if (pqVector.empty())
            throw underflowError("vpriority_queue top(): empty list");

      // return
      return pqVector[maxIndex];
}


// not sure what i need to implement  for this function
int findMaxIndex() const
{

}


-----Not sure what else i am missing in the implementation of the header file
if needed i can supply the test program or anything else that is needed that can help me figure out what i am missing to get this project working--------------

To me this is difficult since i am new to STL and not sure what i am missing in this header file. I sure hope someone can tell me what i need to add to get this header file implemented correctly so my program starts to work. The prgram is due tomorrow and i am really stuck on what i am missing. Thanks all.
ASKER CERTIFIED SOLUTION
Avatar of seet82
seet82

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial