#ifndef QUEUE_CLASS
#define QUEUE_CLASS

#include <iostream.h>
#include <assert.h>

template <class T>
class Queue;

template <class T>
class QueueNode
{
	friend class Queue<T>;
private:
	T data;
	QueueNode<T> *link;
	QueueNode(T d=0,QueueNode<T> *l=NULL):data(d),link(l){}
};

template<class T>
class Queue
{
public:
	Queue():front(NULL),rear(NULL){}
	~Queue();
	void EnQueue(const T & item);
	bool DeQueue(T & item);
	T Get();
	void MakeEmpty();
	int IsEmpty(){return front==NULL;}
private:
	QueueNode<T> *front,*rear;
};

template <class T>
Queue<T>::~Queue()
{
	MakeEmpty();
}

template <class T>
void Queue<T>::MakeEmpty()
{
	QueueNode<T> *p;
	while(front!=NULL)
	{
		p=front;
		front=front->link;
		delete p;
	}
}

template <class T>
void Queue<T>::EnQueue(const T & item)
{
	if(front==NULL)
		front=rear=new QueueNode<T> (item,NULL);
	else
		rear=rear->link=new QueueNode<T> (item,NULL);
}

template <class T>
bool Queue<T>::DeQueue(T & item)
{
	if(front==NULL)
		return false;
	else
	{
		QueueNode<T> *p=front;
		item=p->data;
		front=front->link;
		if(front==NULL)
			rear=NULL;
		delete p;
		return true;
	}
}

template <class T>
T Queue<T>::Get()
{
	assert(!IsEmpty());
	return front->data;
}

#endif