#include <iostream>
using namespace std;

template <class x> class Node{
public:
	x	data;
	Node<x> *next;
};

template <class x> class Queue{
public:
	Queue					();
	//~Queue					();
	void	Enqueue			(x e);
	void	Dequeue			(x& e);
	int		QueueIsFull		();
	int		QueueIsEmpty	();
	Node<x>* MakeNode		(x e);
	//void	QueueRetreive	(x& e);
private:
	Node<x>* rear;
	Node<x>* front;
};

int main(){
	Queue<int> q;
	q.Enqueue(2);
	q.Enqueue(4);
	q.Enqueue(6);
	q.Enqueue(8);

	int e;
	q.Dequeue(e);
	cout << e;
	q.Dequeue(e);
	cout << e;
	q.Dequeue(e);
	cout << e;
	q.Dequeue(e);
	cout << e;

	q.Enqueue(1);
	q.Enqueue(3);
	q.Dequeue(e);
	cout << e;
	q.Dequeue(e);
	cout << e;
	return 0;
}

template <class x> Queue<x>::Queue() {
	rear = NULL;
	front = NULL;
}

template <class x> int Queue<x>::QueueIsEmpty() {
	if (rear == NULL && front == NULL)
		return 1;
	return 0;
}

template <class x> int Queue<x>::QueueIsFull() {
	return 0;
}

template <class x> void Queue<x>::Enqueue(x e) {
	Node<x> *p = MakeNode(e);
	if (QueueIsEmpty()){
		rear = front = p;
	}
	else
	{
		p->next = rear;
		rear = p;
	}
}

template <class x> void Queue<x>::Dequeue(x &e){
	Node<x> *p = new Node<x>;
	Node<x> *q = new Node<x>;
	if (rear == front != NULL){
		p = front;
		e = p->data;
		delete p;
		front = rear = NULL;
	}
	else if (!QueueIsEmpty()){
		p = front;
		q = rear;
		e = p->data;
		while(!(q->next == p) && !(front == rear)){
			q = q->next;
		}
		q->next = NULL;
		front = q;
		delete p;
	}
}

template <class x> Node<x>* Queue<x>::MakeNode(x e) {
	Node<x> *p = new Node<x>;
	p->data = e;
	p->next = NULL;
	return p;
}