template <class T>
struct elem_q
{
	T inf;
	elem_q<T> *link;
};

template <class T>
class queue
{
public:
	queue();
	~queue();
	queue(queue const &);
	queue& operator=(queue const &);
	bool empty() const;
	void InsertElem(T const &);
	int DeleteElem(T &);
	void print();
private:
	elem_q<T> *front, 
		      *rear;
	void copyqueue(queue const &);
	void delqueue();
};

template <class T>
queue<T>::queue()
{
	front = rear = NULL;
}

template <class T>
queue<T>::~queue()
{
	delqueue();
}

template <class T>
queue<T>::queue(queue<T> const &r)
{
	copyqueue(r);
}

template <class T>
queue<T>& queue<T>::operator=(queue<T> const &r)
{
	if (this != &r)
	{
		delqueue();
		copyqueue(r);
	}
	return *this;
}

template <class T>
bool queue<T>::empty() const
{
	return rear == NULL;
}

template <class T>
void queue<T>::InsertElem(T const &x)
{
	elem_q<T> *p = new elem_q<T>;
	p->inf = x;
	p->link = NULL;
	if (rear)
		rear->link = p;
	else
		front = p;
	rear = p;
}

template <class T>
int queue<T>::DeleteElem(T &x)
{
	if (rear == NULL)
		return 0;
	x = front->inf;
	elem_q<T> *p = front;
	if (front == rear)
	{
		front = NULL;
		rear = NULL;
	}
	else
		front = p->link;
	delete p;
	return 1;
}

template <class T>
void queue<T>::print()
{
	T x;
	while (DeleteElem(x))
		cout<<x<<" ";
	cout<<"\n";
}

template <class T>
void queue<T>::delqueue()
{
	T x;
	while (DeleteElem(x)) ;
}

template <class T>
void queue<T>::copyqueue(queue<T> const &r)
{
	front = rear = NULL;
	if (r.rear)
	{
		elem_q<T> *p = r.front;
		while(p)
		{
			InsertElem(p->inf);
			p = p->link;
		}
	}
}