c07p348.txt

Data Abstraction & Problem Solving with C++源码

// *********************************************************
// Implementation file QueueP.cpp for the ADT queue.
// Pointer-based implementation.
// *********************************************************
#include "QueueP.h"  // header file
#include <cstddef>
#include <cassert>

Queue::Queue() : backPtr(NULL), frontPtr(NULL)
{
}  // end default constructor

Queue::Queue(const Queue& Q)
{  // Implementation left as an exercise (Exercise 4).
}  // end copy constructor

Queue::~Queue()
{
   while (!isEmpty())
      dequeue();
   assert ((backPtr == NULL) && (frontPtr == NULL));
}  // end destructor

bool Queue::isEmpty() const
{
   return backPtr == NULL;
}  // end isEmpty

void Queue::enqueue(QueueItemType newItem)
{
   // create a new node
   QueueNode *newPtr = new QueueNode;

  // set data portion of new node
   newPtr->item = newItem;

   newPtr->next = NULL;

   // insert the new node
   if (isEmpty())
      // insertion into empty queue
      frontPtr = newPtr;
   else
      // insertion into nonempty queue
      backPtr->next = newPtr;

   backPtr = newPtr;  // new node is at back
}  // end enqueue

void Queue::dequeue() throw(QueueException)
{
   if (isEmpty())
      throw QueueException("QueueException: empty queue, cannot dequeue");
   else
   {  // queue is not empty; remove front
      QueueNode *tempPtr = frontPtr;
      if (frontPtr == backPtr)   // special case?
      {  // yes, one node in queue
         frontPtr = NULL;
         backPtr = NULL;
      }
      else
         frontPtr = frontPtr->next;

      tempPtr->next = NULL;  // defensive strategy
      delete tempPtr;
   } // end if
}  // end dequeue

void Queue::dequeue(QueueItemType& queueFront) throw(QueueException)
{
   if (isEmpty())
      throw QueueException("QueueException: empty queue, cannot dequeue");
   else
   {  // queue is not empty; retrieve front
      queueFront = frontPtr->item;
      dequeue();  // delete front
   } // end if
}  // end dequeue

void Queue::getFront(QueueItemType& queueFront) const
                     throw(QueueException)
{
   if (isEmpty())
      throw QueueException("QueueException: empty queue, cannot getFront");
   else
      // queue is not empty; retrieve front
      queueFront = frontPtr->item;
}  // end getFront
// End of implementation file.