#ifndef __QList
#define __QList

#include <stdlib.h>

template <class Etype>
class Queue
{
  private:
	struct QueueNode
	{
		int			num;
        	Etype 		data;
		QueueNode 	*Next;
	};
	QueueNode 		*Front;
	QueueNode		*Rear;
	Queue(const Queue &);                   // Prevent copy

  public:
	Queue( ) : Front( NULL ), Rear (NULL) { }   // Initialize pointer
	~Queue( ) { MakeEmpty( ); }                 // Make sure it's gone

    	void Enqueue( const Etype & X, const int & );
    	void Dequeue( );
	const Etype & Getdata( ) const;
	const int Getnum ( ) const;
	int IsEmpty( ) const
		{ return Front == NULL; }      	   // Just check pointer
	int IsFull( ) const
		{ return 0; }                      // Not possible
	void MakeEmpty( );                      
};

template <class Etype>
void Queue<Etype>::Enqueue( const Etype & X, const int & Y )
{
	QueueNode	*temp;

	temp = new QueueNode;                   // Make node
	temp->data = X;
	temp->num = Y;                          // Fill in parts
	temp->Next = NULL;
    	if (Rear != NULL)
		{	Rear->Next = temp;
			Rear = temp; }
    	else Front = Rear = temp;
}

template <class Etype>
void Queue<Etype>::Dequeue( )
{
	QueueNode 	*Old = Front;

	if (IsEmpty())                          // Insure validity
    	{ 	cout << "Attempt to Dequeue from an empty queue.\n";
    		exit(1);   }
	Front = Front->Next;          		// Remove top
    	if (Rear == Old) Rear = NULL;
    	delete Old;
}

template <class Etype>
const Etype & Queue<Etype>::Getdata( ) const
{
    if (IsEmpty())                          // Insure validity
    { 	cout << "Attempt to access Front of empty queue.\n";
    	exit(1);   }
    return Front->data;             // Get front data value
}

template <class Etype>
const int Queue<Etype>::Getnum( ) const
{
    if (IsEmpty())                          // Insure validity
    { 	cout << "Attempt to access Front of empty queue.\n";
    	exit(1);   }
    return Front->num;             // Get front num value
}

template <class Etype>
void Queue<Etype>::MakeEmpty( )
{
    while( !IsEmpty( ) )
    	Dequeue( );                            // Remove an element
}

#endif