Advice on implementing put() function in a c++ templated queue?

Question

I'm trying to implement a queue where I'm not allowed to change the header file definition, which looks like this:

class PQueue
{
  private:

    struct Node
    {
      EType Item;
      unsigned Priority;
      unsigned Identifier;
      Node * Pred;
      Node * Succ;
    };

    Node * Head;    // Pointer to head of chain (front)
    Node * Tail;    // Pointer to tail of chain (back)

  public:

    // Initialize pqueue to empty
    //
    PQueue();

    // De-initialize pqueue
    //
    ~PQueue();

    // Re-initialize pqueue to empty
    //
    void reset();

    // Initialize pqueue using existing pqueue
    //
    PQueue( const PQueue<EType>& );

    // Assign into pqueue from other pqueue
    //
    PQueue<EType>& operator=( const PQueue<EType>& );

    // Display attributes and contents of pqueue
    // (from front to back, or back to front)
    //
    void display( ostream&, Direction ) const;

    // Return number of items in pqueue
    //
    unsigned length() const;

    // Return copy of item at front of pqueue (unless pqueue is empty)
    //
    bool front( EType& ) const;

    // Return copy of item at back of pqueue (unless pqueue is empty)
    //
    bool back( EType& ) const;

    // Insert one item (with specified priority) into pqueue (if possible)
    //
    bool put( const EType&, unsigned );

    // Remove item with highest priority from pqueue (unless pqueue is empty)
    //
    bool get( EType& );

    // Discard item with specified identifier from pqueue (if possible)
    //
    bool discard( unsigned );
};

So far I have these constructors and destructors:

template <typename EType> PQueue::PQueue() {
    Head->Pred = NULL;
    Tail->Succ = NULL;
    Tail->Pred=Head;
    Head->Succ=Tail;
} 

template <typename EType> PQueue::~PQueue() {
    reset();
    delete Head;
    Head = NULL;
    delete Tail;
    Tail = NULL;
}

Now I am stuck on the put(), I have no idea where to start, any help?

Answer 1

You should allocate a node, and hook it into the list.

Like this:

   template <typename EType>
   bool PQueue::put( const EType& et, unsigned pri ) {
      Node *p = new Node ();
      p->Item = et;
      p->priority = pri;
// now hook it into the list
   p->pred = NULL;
   head = p;
   }

However, this is not sufficient, because you don't initialize head and tail correctly in the constructor; to the point that I can't tell if you are creating a singly linked list or a doubly linked list. In your current code, your code acts as if head and tail point to actual nodes, but I don't see where these nodes are (or are created).

Also, some of your code is templated on EType, while other parts are not. You need to be consistent.

Answer 2

Before you move on to put() you need to get your existing constructor and destructor right!

If you are going to be setting the ->Pred or ->Succ of a Node then a node has to first exist. Head and Tail are pointers to Node...not instances of Node, so there's no nodes to operate on:

Matters would be different if Head and Tail were themselves Nodes, but then they would be declared like:

Node Head;    // head node of chain (front)
Node Tail;    // tail node of chain (back)

...instead of:

Node * Head;    // Pointer to head of chain (front)
Node * Tail;    // Pointer to tail of chain (back)

That's technically possible to do, but it's not clear why an empty-and-uninitialized queue implementation would require any nodes to exist at all. If you were creating an unusual queue class which always had at least two elements (for some reason) then you might consider such oddities. But your assignment clearly isn't asking for that.

The rule you want to shoot for is that an empty queue (such as one that has just been constructed) has zero Nodes. Just set the Head and Tail pointers themselves to NULL and you're done:

template <typename EType> PQueue::PQueue() {
    Head = NULL;
    Tail = NULL;
} 

There's a special syntax for initializing members, by the way...and while it doesn't really matter in this case whether you initialize using assignment statements in the code, there are some cases like base class initialization where you have to do it this way:

template <typename EType> PQueue::PQueue() :
    Head (NULL),
    Tail (NULL)
{
} 

So if the rule (or the "invariant") is that empty queues have null heads and tails, then calling reset() should put you in a state where the head and tail are NULL. Yet if the head and tail are NULL, then why are you deleting them in the destructor? It's technically safe:

Is it safe to delete a NULL pointer?

But would have no effect. A reset() call should be sufficient to implement the work of the destructor to release all the allocated nodes of any non-empty queues...and reset() should be smart enough to do nothing if a queue is empty:

template <typename EType> PQueue::~PQueue() {
    reset();
}

As for my advice on proceeding to put()... well... it looks like you need to hit the books a bit and understand foundational issues of the language and data structures. Work through simple linked lists...without templates...and just get one working:

http://en.wikipedia.org/wiki/Linked_list