pqueue1.h:
The header file for this first version of the PriorityQueue
class. Actually, you don't have to write much of this file.
Just copy our version from
pqueue1.h
and add your name and other information at the top.
If some of your member functions are implemented as inline
functions, then you may put those implementations in this file too.
pqueue1.cxx:
The implementation file for the
PriorityQueue class. You will write all of this file, which will
have the implementations of all the PriorityQueue's member functions.
Also, remember that the PriorityQueue's
linked list consists of dynamic memory, so you will need to define a
copy constructor, an assignment operator, and a destructor.
pqtest.cxx:
A simple interactive test program.
pqexam1.cxx:
A non-interactive test program that will
be used to grade the correctness of your PriorityQueue class.
You will store the items on a linked list, where each node contains both an item and the item's priority, as shown here:
struct Node { // Note: Item is defined with a typedef in the PriorityQueue class PriorityQueue::Item data; unsigned int priority; Node *link; };
This Node definition appears in the header file pqueue1.h, immediately after the PriorityQueue class definition. Neither class needs to be a template class (instead, the Item type is defined as an int by using a typedef within the PriorityQueue class definition).
This approach is different from the approaches discussed in Section 8.4 since all the items are stored on a single linked list. I suggest that you maintain the linked list in order from highest to lowest priority. If there are several items with equal priority, then the one that came in first will be in front of the others. If you choose to follow this suggestion, then make sure that you have a clearly stated invariant that expresses this way of storing the items.
Because the linked list is kept in order, the get_front operation is simple. It merely gets the head item of the linked list. On the other hand, the insert operation requires some amount of work, making sure that the new entry goes at the correct spot in the linked list. A new entry must go after any existing entries with a higher or equal priority.