#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>

template <class I>
class Queue
{

	//Our data in the linklist is stored in nodes
	//whichs contains data and next pointers
	struct Node
	{
		I element;
		Node* next;
		Node* prev;
	};

	//head pointer which points to the first node in the SLL
	Node* m_head;
	Node* m_tail;

public:

	//constructors and destructors
	Queue(void);
	~Queue(void);

	void PUSH(I value);
	void POP();
	I FRONT();
	void CLEAR();
	void Print();
};
#endif

template <class I> Queue<I>::Queue(void)
{
	m_head=0;
	m_tail = 0;
}
template <class I> Queue<I>::~Queue(void)
{

}

//Pushs a node in the back of the list
template <class I> void Queue<I>::PUSH(I value)
{
	if(!m_head)
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->next = 0;

		n->prev = 0;

		// Point head to new headnode
		m_head = n;
		m_tail = n;
	}
	else
	{
		// Dynamically create a new node
		Node* n = new Node;

		//Set N to value to passed node into fuction
		n->element = value;

		// Set the pointer to the current head
		n->prev = m_tail;
		m_tail->next = n;
		n->next = 0;

		// Point head to new headnode
		m_tail = n;
	}
}

//removes from the list
template <class I> void Queue<I>::POP()
{
	// create a pointer (tmp) that points to head
	Node* tmp = m_head;

	// move head to tmps next node
	m_head = tmp->next; //alternatively, m_head = m_head->next

	//delete tmp's node
	m_head->prev = 0;

	delete tmp;
}

//puts the node in front of the line
template <class I> I Queue<I>::FRONT()
{
	return m_head->element;
}

//clears the entire node structure
template <class I> void Queue<I>::CLEAR()
{
	while(m_head)
	{

		// create a pointer (tmp) that points to head
		Node* tmp = m_head;

		// move head to tmps next node
		m_head = tmp->next; //alternatively, m_head = m_head->next

		//delete tmp's node
		delete tmp;
	}		
}

template <class I> void Queue<I>::Print()
{
	Node* tmp = m_head;
	while(tmp)
	{
		cout << tmp->element << " <- ";

		tmp = tmp->next;
	}
	cout << "X\n";
}