Solved

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

Posted on 2006-04-29

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.