#include<iostream.h>
#include<stdlib.h>

void Exception(int Condition,   char *ErrorMsg){
	if(Condition){cerr << ErrorMsg << endl; abort();}
}

template<class ElemType>
class AbsQueue{
	public:
		AbsQueue(){}  //默然构造函数
		virtual ~AbsQueue(){}  //析构函数
		virtual bool IsEmpty() const = 0;  //判栈空
		virtual bool IsFull() const = 0;   //判栈满
		virtual void MakeEmpty() = 0;     //将栈清空
		virtual void EnQueue( ElemType &x) = 0;  //进栈
		virtual void DeQueue() = 0;        //出栈
		virtual const ElemType &Front()  = 0; //取顶点元素
	private:
		AbsQueue(const AbsQueue &){};  //冻结复制构造函数
};

template<class ElemType>
class Queue;  //前向说明

template<class ElemType>
class ListNode{
	friend class Queue<ElemType>;  //便于访问结点的私有成员
	private:
		ListNode<ElemType> *Next;  //指向下一个结点
		ElemType Element;   //结点数据
	public:
		ListNode(const ElemType &E, ListNode<ElemType> *N = 0):Element(E), Next(N)
		{}; //构造函数
		ListNode():Next(0){}; //构造函数
		~ListNode(){};  //析构函数
};

template<class ElemType>
class Queue:public AbsQueue<ElemType>{
	public:
		Queue():front(0),rear(0){};  //构造函数
		~Queue(){ MakeEmpty();}  //析构函数
		bool IsEmpty() const {return front == 0;}  //判栈空
		bool IsFull() const {return false;}   
		void MakeEmpty();     //将栈清空
		void EnQueue( ElemType &x);  //进栈
		void DeQueue();        //出栈
		const ElemType &Front(); //取顶点元素
		const Queue &operator=(const Queue &R);
	private:
		ListNode<ElemType> *front;             //栈顶指针
		ListNode<ElemType> *rear;             //栈顶指针
};

template<class ElemType>
const ElemType &Queue<ElemType>::Front(){ //读取栈顶结点
	Exception(IsEmpty(), "There is not a node!");
	return front->Element;
}

template<class ElemType>
void Queue<ElemType>::EnQueue( ElemType &x){
	if(IsEmpty()) front = rear = new ListNode<ElemType>(x);
	else rear = rear->Next = new ListNode<ElemType>(x);
}

template<class ElemType>
void Queue<ElemType>::DeQueue(){  //将栈顶元素出栈
	Exception(IsEmpty(), "Queue is underflow!");
	ListNode<ElemType> *q = front;
	front = front->Next;
	delete q;
}

template<class ElemType>
const Queue<ElemType> &Queue<ElemType>::operator=(const Queue<ElemType> &R){
	if(this == &R) return *this;
	MakeEmpty();
	if(R.IsEmpty()) return *this;
	ListNode<ElemType> *p = new ListNode<ElemType>(R.front->Element);
	ListNode<ElemType> *Rp = R.front->Next;
	front = p;
	while(Rp != 0){
		p->Next = new ListNode<ElemType>(Rp->Element);
		p = p->Next;
		if(Rp->Next == 0) rear = p;
		Rp = Rp->Next;
	}
	return *this;
}

template<class ElemType>
void Queue<ElemType>::MakeEmpty(){
	ListNode<ElemType> *Ptr;
	ListNode<ElemType> *NextNode;
	for(Ptr = front; Ptr != 0; Ptr = NextNode){
		NextNode = Ptr->Next;
		delete Ptr;
	}
	front = rear = 0;
}

void main()
{

}