#pragma once
template <typename T>
class CQueue
{
public:
	CQueue(void);
	~CQueue(void);
	
	T Top(void);
	void Pop(void);
	void Push(const T &value);
	int GetLength();
	bool IsExisted(const T& value);
private:
	class CNode
	{
	public:
		CNode():next(0)
		{}
		T key;
		CNode* next;
	};
	CNode* m_head;
	CNode* m_tail;
	int m_length;
};
template <typename T>
CQueue<T>::CQueue()
:m_head(0),m_tail(0),m_length(0)
{
}

template <typename T>
CQueue<T>::~CQueue()
{
	CNode* toDelete=m_head;
	while(toDelete!=0)
	{
		m_head=toDelete->next;
		delete toDelete;
		toDelete=m_head;
	}
	m_head=0;
	m_tail=0;
}


template <typename T>
T CQueue<T>::Top()
{
	return m_head->key;
}

template <typename T>
void CQueue<T>::Pop()
{
	if(m_head==0)
		return;
	
	CNode* toDelete=m_head;
	
	if(toDelete==m_tail)
		m_tail=0;
	m_head=m_head->next;
	delete toDelete;
	m_length--;
}

template <typename T>
void CQueue<T>::Push(const T &value)
{
	if(IsExisted(value))
		return;

	CNode* newNode=new CNode();
	newNode->key=value;

	if(m_head==0)
	{
		m_head=newNode;
		m_tail=m_head;
	}
	else
	{
		m_tail->next=newNode;
		m_tail=m_tail->next;
	}
	m_length++;
}

template <typename T>
int CQueue<T>::GetLength()
{
	return m_length;
}

template <typename T>
bool CQueue<T>::IsExisted(const T& value)
{
	CNode* now=this->m_head;
	while(now!=0)
	{
		if(now->key==value)
			return true;
		now=now->next;
	}
	return false;
}