#include <iostream>
using namespace std;

template <class T>
class Node {

	public:
		Node(T e, Node<T>* n) {
			element = e;
			next = n;
		}
		void set_next(Node<T>* n) {next = n;}
		Node<T>* get_next() { return next;}
		T get_element() { return element;}
	private:
		T element;
		Node<T>* next;
};

template <class T>
class Queue {

	public:
		Queue() {
			first = NULL;
			last = NULL;
		}
		void enqueue(T element);
		T dequeue();
		bool is_empty() {
			return (first == NULL);
		}
	private:
		Node<T>* first;
		Node<T>* last;
};

template <class T> 
void Queue<T>::enqueue(T element) {
	
	Node<T>* old_last = last;
	last = new Node<T>(element, NULL);	
	if (old_last == NULL) first = last;
	else old_last->set_next(last);
}

template <class T> 
T Queue<T>::dequeue() {
	if (first==NULL)
		throw "Dequeue from empty queue.";
	T e = first->get_element();
	Node<T>* old_first = first;
	first = first->get_next();
	if (first == NULL) last ==NULL;
	delete old_first;
	return e;
}

int main() {

	Queue<int> w;
	w.enqueue(19);
	w.enqueue(1);
	w.enqueue(42);
	w.enqueue(13);
	while (! w.is_empty())
		cout << w.dequeue() << " ";
	cout << endl;
	return 0;
}