Program #6

Rewrite the PriorityQueue class template from Program #4 with a new implementation. The public interface may not change in any way. What changes is the implementation, which will now use a singly-linked list (as was done in the stack and queue examples online). he linked list will be sorted, with the smallest item at the front. This makes findMin and removeMin relatively easy, but insert somewhat more difficult. I will provide a test program and you must use it, unmodified, and provide output.

The PriorityQueue Template Interface

Here is the interface:

template <class Comparable>
class PriorityQueue
{
  public:
    PriorityQueue( );
    ~PriorityQueue( );
    PriorityQueue( const PriorityQueue & other );

    bool isEmpty( ) const;
    Comparable findMin( ) const;

    void makeEmpty( );
    void insert( const Comparable & x );
    void removeMin( );
    void removeMin( Comparable & minValue );

    const PriorityQueue & operator=( const PriorityQueue & rhs );

  private:
    // You will need to provide this
};

Notice that you will need to write a destructor, copy constructor, and copy assignment operator.

Due Date

This program is due on Tuesday October 26.