#ifndef QUEUE_H
#define QUEUE_H
template <class Etype>
class Queue {
public:
	virtual ~Queue(){}
	/* Constructoras */
	virtual void Empty() = 0;
	// retorna la cola vacía
	virtual void Enqueue(const Etype &x) = 0;
	/* retorna una cola con último elemento x y el
	resto de la cola queda igual */
	virtual bool IsEmpty() = 0;
	// retorna true si la cola es vacía
	virtual Etype Front() = 0;
	/* pre : la cola no es vacía
	post: retorna el primer elemento */
	virtual void Dequeue() = 0;
	/* pre : la cola no es vacía
	post: retorna la cola resultado de borrar el primer
	elemento */
};
#endif

////////////////////////////////////////////////////////////////////////////


#ifndef QUEUEIMP_H
#define QUEUEIMP_H
#include "Queue.h"

template <class Etype>
class QueueImp: public Queue<Etype>{
private:

	struct nodoQ{
		Etype dato;
		nodoQ* sig;
	};

	typedef nodoQ* PtrQueue;
	PtrQueue raiz, fin;
	void DeleteQueue();

public:
	QueueImp();
	~QueueImp();	
	void Empty();	
	void Enqueue(const Etype &x);	
	bool IsEmpty();	
	Etype Front();
	void Dequeue();
};

#include "QueueImp.cpp"
#endif


////////////////////////////////////////////////////////////////////////////
#ifndef QUEUEIMP_CPP
#define QUEUEIMP_CPP

#include "QueueImp.h"
#include <assert.h>

template <class Etype>
void QueueImp<Etype> :: DeleteQueue(){
	while(!IsEmpty())
		Dequeue();
};

template <class Etype>
QueueImp<Etype> :: QueueImp(){
	raiz = new nodoQ;
	raiz ->sig = NULL;
	fin = raiz;
};

template <class Etype>
QueueImp<Etype> :: ~QueueImp(){
	DeleteQueue();
	delete[] raiz;
};

template <class Etype>
void QueueImp<Etype> :: Empty(){
	DeleteQueue();
	raiz -> sig = NULL;
	fin = raiz;
};

template <class Etype>
void QueueImp<Etype> :: Enqueue(const Etype &x){
	nodoQ* n = new nodoQ;
	n->dato = x;
	n-> sig = NULL;
	fin -> sig = n;
	fin = fin -> sig;
};

template <class Etype>
bool QueueImp<Etype> :: IsEmpty(){
	return raiz == fin;
};

template <class Etype>
Etype QueueImp<Etype> :: Front(){
	assert(raiz != fin);
	return raiz -> sig -> dato;
};

template <class Etype>
void QueueImp<Etype> :: Dequeue(){
	assert(raiz != fin);
	PtrQueue temp = raiz;
	raiz = raiz -> sig;
	delete temp;
};

#endif