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>::vprior ity_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(c onst 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.
// 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>::vprior
{
recomputeMaxIndex=true;
}
// return the size of the priority queue
template <typename T>
int vpriority_queue<T>::size()
{
return pqVector.size();
}
// return true if the priority queue is empty and false
// otherwise
template <typename T>
bool vpriority_queue<T>::empty(
{
return pqVector.empty();
}
// insert a new item in the priority queue
template <typename T>
void vpriority_queue<T>::push(c
{
// 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>
{
// check for an empty priority queue
if (pqVector.empty())
throw underflowError("vpriority_
// 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_
// 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_
// 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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.