lab 3: 15-113 Fall 2000

Lab 3: A Linked Implementation of a Priority Queue

Due Date: Tue 14 Nov, 23:59.

Background:

Lab 3 will provide you additional opportunity to work with linked lists. You are to implement a priority queue of integers via a sorted linked list (smallest to highest). Thus, for this assignment, the smallest integer has the "highest priority". The operations you are to implement include:

Insert - inserts a new item in the correct place in the priority queue. An item with the same priority as one already in the priority queue should be inserted after the last occurrence of the equal priority.
DeleteMin - returns the item that has the highest priority and then deletes it from the priority queue. Must report an error if called on an empty queue.
IsEmpty - 'nuff said
FindMin - returns the item that has the highest priority. Must report an error if called on an empty queue.
operator<< - displays the priority queue

We will subsequently template this class in Lab 4.

What You'll Need

Download the lab3.zip file from the 15-113 course web site. Save the zip file to your temp directory and unzip the files. You should see the following files:

lab3.mcp
p-queue.h
p-queue.cpp
pq-test.cpp

Assignment

You are implementing a priority queue of integers with a sorted linked list. Open the lab3.mcp file and look at the filenames listed inside. If you open up the p-queue.cpp file, you'll notice that it's pretty empty. You are to complete the implementation of all of the member functions found in the p-queue.h header file, including the destructor, copy constructor, and assignment operator (do these 3 after you have the basic priority queue working). You'll find that implementing the private helper function MakeEmpty will make the destructor and assignment operator a little easier (see below).

Remember that all member function definitions in the .cpp file must be prefaced with PQueue:: to resolve the scope of the function correctly. Also note that operator<< is a friend, not a member function. Thus, if you need to declare a Node* inside the definition of operator<<, you'll have to resolve it with PQueue:: as well (i.e., PQueue::Node* p).

You can implement Insert either iteratively or recursively. It will probably be easier to define a private helper function if you choose to implement the Insert recursively. Remember also the general form of the copy constructor:


{
    initialize private data as the default constructor would
    *this = pq;
}

And the general form of the assignment operator:


{
    if (this != &rhs)
    {
        MakeEmpty();  //no memory leak here!

        //Initialize self if MakeEmpty() didn't

        //Explicitly copy into new memory all of rhs's data
    }
    return *this;
}

You should make no changes to pq-test.cpp (other than to remove the comments to test the assignment operator and copy constructor once you've implemented them). You will not need to run this in a DOS window as we are not using a command-line interface.

Handing in your Solution

Your solution should be in the form of a .zip file. When we grade your solution we will unzip the folder and execute the project.

Your Solution zip file must contain (only) the following files

lab3.mcp (the project)
p-queue.h
p-queue.cpp

You should not include a copy of the pq-test.cpp file as it should not be changed. Since you may have changed p-queue.h (by adding a helper function), you should include it in your handin.

Use the Intro Programming dropoff form to submit your zip file.