/*
 * FILE: queue-linked.h
 *
 *      A template class definition for a Stack ADT 
 *      using an array representation
 *
 *  From Kruse&Ryba: _Data Structure and Program Design in C++_
 *
 *  Modified: spc
 *
 * DESCRIPTION: Queue is a queue (first-in, first-out) container.
 *   The template parameter Node_entry is the type of items contained.
 *
 * OPERATIONS:
 *   Queue()
 *     Post: Initializes an empty queue.
 *
 *   ~Queue()
 *     Post: Destroys an existing queue.
 *
 *   Queue(const Queue&)
 *     Post: Initializes a queue as a deep copy of the argument
 *
 *   enqueue(item)
 *     Pre:  None
 *     Post: A copy of item has been added to back of Queue;  if out-of-memory
 *		condition is detected, returns overflow
 *
 *   dequeue(item)
 *     Pre:  Queue not empty
 *     Post: entry at front of queue has been removed and returned in item
 *
 *   empty()
 *     Post: Returns true if queue empty, false otherwise
 *
 *   operator=(const Queue&)
 *     Post: Overwrites queue on left-hand side of operator with deep copy of
 *           queue on right-hand side
 *
 * SEMANTICS:
 *   This class has reference semantics and requires that operator=
 *   and the copy constructor be overloaded or not used.
 *
 */

#ifndef __QUEUE
#define __QUEUE

template <class Node_entry>
struct Node {
   //  constructors
   Node() { next = NULL; }
   Node(Node_entry item, Node *add_on = NULL) 
	{ entry = item; next = add_on; }

   // data members
   Node_entry entry;
   Node *next;
};

template <class Queue_entry>
class Queue {
public:
   Queue();
   Queue(const Queue<Queue_entry> &original);
   ~Queue();

   bool empty() const;
   void enqueue(const Queue_entry &item);
   void dequeue(Queue_entry &item);
   void getFront(Queue_entry &item);

   Queue<Queue_entry>& operator =(const Queue<Queue_entry> &original);

protected:
   Node<Queue_entry> *front, *back;
};

#endif