queue.h

单项链表的实现

// Queue.h: interface for the CQueue class.
//
/********************************************************************
	created:	2004/08/09
	created:	9:8:2004   23:33
	file base:	queue
	file ext:	h
	author:		阙荣文(北方工业大学计算机2000级)
	
	purpose:	构建一个通用的,独立于MFC的单向链表
				我想c++的标准库模板应该也有类似功能的类,但是我还是决定自己实现
				这样可以使用我自己喜欢的参数调用方式.
				希望对用同样需求的编程爱好者有用
*********************************************************************/

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

#if !defined(AFX_QUEUE_H__57C46373_D485_43F2_998C_D3EA4984E59A__INCLUDED_)
#define AFX_QUEUE_H__57C46373_D485_43F2_998C_D3EA4984E59A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
template <class T> 
class CQueue  
{
public:
	CQueue();
	virtual ~CQueue();

	int		AddHead(T* pT);
	int		AddTail(T* pT);
	int		Insert(int nIndex,T* pElement);		//在第nIndex个元素后插入
	
	int		GetSize();
	BOOL	GetAt(int nIndex,T& Element);
	
	BOOL	RemoveAt(int nIndex);
	void	RemoveAll();
	BOOL	RemoveHead();
	BOOL	RemoveTail();

	int		Find(T Element);
	BOOL	GetFirstNode(T &Element);
	BOOL	GetNextNode(T &Element);
protected:
	struct Node{
		Node* pNext;
		T Data;
	};
	int m_nSize;			//队列的大小
	Node* m_pHead;			//队列头指针
	Node* m_pTail;			//队列尾指针
	Node* m_pCurrentNode;	//当前节点的指针
};

//因为是模板类,所以所有函数的实现代码必须一起放在头文件中

template <class T> 
CQueue<T>::CQueue()
{
	m_nSize = 0;
	m_pHead = NULL;
	m_pTail = NULL;
	m_pCurrentNode = NULL;	
}

template <class T> 
CQueue<T>::~CQueue()
{
	RemoveAll();
}

template <class T> 
int CQueue<T>::AddHead(T* pT)
{
	ASSERT(pT);
	Node *pNewNode = new Node;
	pNewNode->Data = *pT;
	pNewNode->pNext = m_pHead;
	m_pHead = pNewNode;
	m_nSize++;
	if(m_nSize == 1)
	{
		m_pTail = m_pHead;
	}
	return m_nSize;
}

template <class T> 
int CQueue<T>::AddTail(T* pT)
{
	ASSERT(pT);
	Node *pNewNode = new Node;
	pNewNode->Data = *pT;
	if(m_pTail != NULL)
	{
		m_pTail->pNext = pNewNode;
	}
	m_pTail = pNewNode;
	m_nSize++;
	if(m_nSize == 1)
	{
		m_pHead = m_pTail;
	}
	m_pTail->pNext = NULL;
	return m_nSize;
}

template <class T>
int CQueue<T>::Insert(int nIndex,T *pElement)
{
	int nRet = 0;
	if(nIndex < 0 || nIndex >= m_nSize || pElement == NULL)
	{
		nRet = -1;
	}
	else
	{
		T *pNode = m_pHead;
		int i = 0;
		while(pNode && i < nIndex)
		{
			pNode = pNode->pNext;
			i++;
		}
		T *pNewNode = new T;
		pNewNode->Data = pElement->pData;
		
		pNewNode->pNext = pNode->pNext;
		pNode->pNext = pNewNode;
		if(pNewNode->pNext == NULL)
		{
			m_pTail = pNewNode;
		}
		m_nSize++;
		nRet = m_nSize;
	}
	return nRet;
}

template <class T>
int CQueue<T>::GetSize()
{
	return m_nSize;
}

template <class T>
BOOL CQueue<T>::GetAt(int nIndex,T& Element)
{
	if(nIndex < 0 || nIndex >= m_nSize) return FALSE;
	Node *pNode = m_pHead;
	for(int i = 1; i <= nIndex; i++)
	{
		pNode = pNode->pNext;
	}
	Element = pNode->Data;
	return TRUE;
}

template <class T>
BOOL CQueue<T>::RemoveAt(int nIndex)
{
	if(nIndex < 0 || nIndex >= m_nSize) return FALSE;
	
	Node *pNode = m_pHead,*pPreNode = NULL;
	for(int i = 1; i <= nIndex; i++)
	{
		pPreNode = pNode;
		pNode = pNode->pNext;
	}
	if(pPreNode != NULL)
	{
		pPreNode->pNext = pNode->pNext;
	}
	if(nIndex == 0)
	{
		m_pHead = pNode->pNext;
	}
	if(nIndex == m_nSize -1)
	{
		m_pTail = pPreNode;
	}
	if(pNode == m_pCurrentNode)
	{
		m_pCurrentNode = NULL;
	}
	delete pNode;
	m_nSize--;
	
	if(m_nSize ==0)
	{
		m_pHead = NULL;
		m_pTail = NULL;
	}
	return TRUE;
}

template <class T>
BOOL CQueue<T>::RemoveHead()
{
	return RemoveAt(0);
}

template <class T>
BOOL CQueue<T>::RemoveTail()
{
	return RemoveAt(m_nSize - 1);
}

template <class T>
void CQueue<T>::RemoveAll()
{
	Node *pNode = m_pHead;
	while(pNode != NULL)
	{
		Node* pTempNode = pNode->pNext;
		delete pNode;
		pNode = pTempNode;
	}
	m_nSize = 0;
	m_pTail = NULL;
	m_pHead = NULL;
	m_pCurrentNode = NULL;
}

template <class T>
int CQueue<T>::Find(T Element)
{
	Node *pNode = m_pHead;
	for(int i = 0; i < m_nSize; i++)
	{
		if(pNode->Data == Element)
		{
			return i;
		}
		pNode = pNode->pNext;
	}
	return -1;
}

template <class T>
BOOL CQueue<T>::GetFirstNode(T &Element)
{
	BOOL bRet = FALSE;
	if(m_pHead)
	{
		m_pCurrentNode = m_pHead;
		Element = *m_pCurrentNode;
		m_pCurrentNode = m_pCurrentNode->pNext;
		bRet = TRUE;
	}
	else
	{
	}
	return bRet;
}

template <class T>
BOOL CQueue<T>::GetNextNode(T &Element)
{
	BOOL bRet = FALSE;
	if(m_pCurrentNode)
	{
		Element = *m_pCurrentNode;
		m_pCurrentNode = m_pCurrentNode->pNext;
		bRet = TRUE;
	}
	else
	{
	}
	return bRet;
}

#endif