Code Listings Chapter 14

Listing 14-1  The header file for the class ListQueue

/** ADT queue: ADT list implementation.
@file ListQueue.h */
#ifndef _LIST_QUEUE
#define _LIST_QUEUE
#include "QueueInterface.h"
#include "LinkedList.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class ListQueue:public QueueInterface < ItemType >
{
private:
  LinkedList < ItemType > *listPtr;	// Pointer to list of queue items

public:
  ListQueue ();
  ListQueue (const ListQueue & aQueue);

  ~ListQueue ();
  bool isEmpty () const;

  bool enqueue (const ItemType & newEntry);

  bool dequeue ();

  /** @throw PrecondViolatedExcep if queue is empty. */
  ItemType peekFront () const throw (PrecondViolatedExcep);

};  // end ListQueue

#include "ListQueue.cpp"
#endif

Listing 14-2 The implementation file for the class ListQueue

/** ADT queue: ADT list implementation.
@file ListQueue.cpp */
#include "ListQueue.h"		// Header file
template < class ItemType > ListQueue < ItemType >::ListQueue ()
{
  listPtr = new LinkedList < ItemType > ();
}				// end default constructor

template < class ItemType >
  ListQueue < ItemType >::ListQueue (const ListQueue & aQueue):
listPtr (aQueue.listPtr)
{
}				// end copy constructor

template < class ItemType > ListQueue < ItemType >::~ListQueue ()
{
}				// end destructor

template < class ItemType > bool ListQueue < ItemType >::isEmpty () constconst
{
  return listPtr->isEmpty ();
}				// end isEmpty

template < class ItemType >
  bool ListQueue < ItemType >::enqueue (const ItemType & newEntry)
{
  return listPtr->insert (listPtr->getLength () + 1, newEntry);
}				// end enqueue

template < class ItemType > bool ListQueue < ItemType >::dequeue ()
{
  return listPtr->remove (1);
}				// end dequeue

template < class ItemType >
  ItemType ListQueue < ItemType >::peekFront () constconst
throw (PrecondViolatedExcep)
{
  if (isEmpty ())
    throw PrecondViolatedExcep ("peekFront() called with empty queue.");
// Queue is not empty; return front
  return listPtr->getEntry (1);
}				// end peekFront

// end of implementation file

Listing 14-3  The header file for the class LinkedQueue

/** ADT queue: Link-based implementation.
@file LinkedQueue.h */
#ifndef _LINKED_QUEUE
#define _LINKED_QUEUE
#include "QueueInterface.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class LinkedQueue:public QueueInterface < ItemType >
{
private:
// The queue is implemented as a chain of linked nodes that has
// two external pointers, a head pointer for the front of the queue
// and a tail pointer for the back of the queue.
  Node < ItemType > *backPtr;
  Node < ItemType > *frontPtr;
public:
  LinkedQueue ();
  LinkedQueue (const LinkedQueue & aQueue);

  ~LinkedQueue ();
  bool isEmpty () const;

  bool enqueue (const ItemType & newEntry);

  bool dequeue ();

/** @throw PrecondViolatedExcep if the queue is empty */
  ItemType peekFront () const throw (PrecondViolatedExcep);
};				// end LinkedQueue

#include "LinkedQueue.cpp"
#endif

Listing 14-4  The header file for the class ArrayQueue

/** ADT queue: Circular array-based implementation.
@file ArrayQueue.h */
#ifndef _ARRAY_QUEUE
#define _ARRAY_QUEUE
#include "QueueInterface.h"
#include "PrecondViolatedExcep.h"
const int MAX_QUEUE = 50;

template < class ItemType > class ArrayQueue:public QueueInterface < ItemType >
{
private:
  ItemType items[MAX_QUEUE];	// Array of queue items
  int  front;			// Index to front of queue

  int  back;			// Index to back of queue

  int  count;			// Number of items currently in the queue

public:
  ArrayQueue ();
// Copy constructor and destructor supplied by compiler
  bool isEmpty () const;

  bool enqueue (const ItemType & newEntry);

  bool dequeue ();

/** @throw PrecondViolatedExcep if queue is empty. */
  ItemType peekFront () const throw (PrecondViolatedExcep);
};				// end ArrayQueue

#include "ArrayQueue.cpp"
#endif

Listing 14-5  The implementation file for the class ArrayQueue

/** ADT queue: Circular array-based implementation.
@file ArrayQueue.cpp */
#include "ArrayQueue.h"		// Header file
template < class ItemType > ArrayQueue < ItemType >::ArrayQueue ():front (0), back (MAX_QUEUE - 1), count (0)
{
}				// end default constructor

template < class ItemType > bool ArrayQueue < ItemType >::isEmpty () constconst
{
  return count == 0;
}				// end isEmpty

template < class ItemType > bool ArrayQueue < ItemType >::enqueue (const ItemType & newEntry)
{
  bool result = false;

  if (count < MAX_QUEUE)
    {
// Queue has room for another item
      back = (back + 1) % MAX_QUEUE;
      items[back] = newEntry;
      count++;
      result = true;
    }				// end if
  return result;
}				// end enqueue

template < class ItemType > bool ArrayQueue < ItemType >::dequeue ()
{
  bool result = false;

  if (!isEmpty ())
    {
      front = (front + 1) % MAX_QUEUE;
      count -;
      result = true;
    }				// end if
  return result;
}				// end dequeue

template < class ItemType > ItemType ArrayQueue < ItemType >::peekFront () constconst throw (PrecondViolatedExcep)
{
// Enforce precondition
  if (isEmpty ())
    throw PrecondViolatedExcep ("peekFront() called with empty queue");

// Queue is not empty; return front
  return items[front];
}				// end peekFront

Listing 14-6 A header file for the class SL_PriorityQueue .

/** ADT priority queue: ADT sorted list implementation.
@file SL_PriorityQueue.h */
#ifndef _PRIORITY_QUEUE
#define _PRIORITY_QUEUE
#include "PriorityQueueInterface.h"
#include "LinkedSortedList.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class SL_PriorityQueue:public PriorityQueueInterface < ItemType >
{
private:
  LinkedSortedList < ItemType > *slistPtr;	// Pointer to sorted list of
							// items in the priority queue
public:
  SL_PriorityQueue ();
  SL_PriorityQueue (const SL_PriorityQueue & pq);

  ~SL_PriorityQueue ();
  bool isEmpty () const;

  bool add (const ItemType & newEntry);

  bool remove ();

/** @throw PrecondViolatedExcep if priority queue is empty. */
  ItemType peek () const throw (PrecondViolatedExcep);
};				// end SL_PriorityQueue

#include "SL_PriorityQueue.cpp"
#endif