Sample Programming Assignment
Chapter 8
Queues
Preliminary Version

Note:

Chapter 8 Assignment 
Implement pqueue.cxx and and an interactive test program for the PriorityQueue
class described below.

Your PriorityQueue class for this assignment will use a DOUBLY linked list to
store the items. The Node data type for the doubly linked list is defined in
pqueue.h along with the PriorityQueue class.  In order for you to further
learn how to manipulate pointers, I would like for you to write all the member
functions from scratch (not using the linked list toolkit).

Also, remember that the doubly linked list consists of dynamic memory, so you
will need to define a copy constructor, an assignment operator, and a
destructor.

// FILE: pqueue.h
// TEMPLATE CLASS PROVIDED: PriorityQueue (a priority queue of items)
//
// TYPEDEF for the PriorityQueue class:
//   typedef _____ Item 
//     The type Item is the data type of the items in the Priority Queue.
//     It may be any of the C++ built-in types (int, char, etc.), or a class 
//     with a default constructor, a copy constructor, and assignment operator.
//
// CONSTRUCTOR for the PriorityQueue class:
//   PriorityQueue( )
//     Postcondition: The PriorityQueue has been initialized with no Items.
//
// MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class:
//   void insert(const Item& entry, unsigned int priority)
//     Postcondition: A new copy of entry has been inserted with the specified
//     priority.
//
//   Item get_front( )
//     Precondition: size( ) > 0.
//     Postcondition: The highest priority item has been returned and has been
//     removed from the PriorityQueue. (If several items have equal priority,
//     then the one that entered first will come out first.)
//
//   void clear( )
//     Postcondition: All items from the priority queue have been removed.
//
// CONSTANT MEMBER FUNCTIONS for the PriorityQueue class:
//   size_t size( ) const
//     Postcondition: Return value is the total number of items in the
//     PriorityQueue.
//
//   bool is_empty( ) const
//     Postcondition: Return value is true if the PriorityQueue is empty.
//
// VALUE SEMANTICS for the PriorityQueue class:
//   Assignments and the copy constructor may be used with
//   PriorityQueue objects

#ifndef PQUEUE_H
#define PQUEUE_H
#include <stdlib.h> // Provides size_t

    class DNode; // This will be completely defined below.

    class PriorityQueue
    {
    public:
        // TYPEDEF
        typedef int Item;
        // CONSTRUCTORS and DESTRUCTOR 
        PriorityQueue( );
        PriorityQueue( const PriorityQueue& source);
        ~PriorityQueue( );
        // MODIFICATION MEMBER FUNCTIONS 
        void insert(const Item& entry, unsigned int priority);
        Item get_front( );
	void clear( );
        void operator =(const PriorityQueue& source);
        // CONSTANT MEMBER FUNCTIONS 
        size_t size( ) const;
        bool is_empty( ) const;
    private:
        // Note: head_ptr is the head pointer for a doubly linked list that
        // contains the items along with their priorities. These nodes are
        // kept in order from highest priority (at the head of the list)
        // to lowest priority (at the tail of the list). The private member
        // variable, many_nodes, indicates how many nodes are on the list.
        // The data type DNode is completely defined below.
        DNode *head_ptr;
        size_t many_nodes;

    };

    class DNode
    {   // Node for a doubly linked list
        PriorityQueue::Item data;
        unsigned int priority;
        DNode *forelink;
        DNode *backlink;
	// FRIENDS
	friend class PriorityQueue;
    };

#endif