以下是实现基于模板的队列。是基于单链表的结构。采用尾插法实现。
template<class Type>
class Queue
{
public:
Queue();
~Queue();
struct NODE
{
struct NODE * next;//前一个节点的地址指针
Type Item;//数据项
};
NODE m_HeadNode;//头结点,不存储任何数据,初始化时上一节点地址为空
NODE* m_pHead,*m_pTail;//队头和队尾指针,遍历指针
public:
bool In(const Type& Item);//从队尾进入队列
Type Out();//从对头出列
bool IsEmpty(){return m_pHead==m_pTail;};//队列是否为空,用在出队时的检测
};
template<class Type>
Queue<Type>::Queue()
{
//初始化头结点和指针
m_HeadNode.next=NULL;
m_HeadNode.Item =0;
m_pHead = m_pTail = &m_HeadNode;
}
template<class Type>
Queue<Type>::~Queue()
{
}
template<class Type>
bool Queue<Type>::In(const Type& Item)
{
//分配节点内存,并进行连接
NODE* pTemp = (NODE*)malloc(sizeof(NODE));
if (!pTemp)return false;
pTemp->next = NULL;
pTemp->Item = Item;
m_pTail->next = pTemp;
m_pTail = pTemp;
return true;
}
template<class Type>
Type Queue<Type>::Out()
{
//出队,并将值返回
if (IsEmpty())return false;
NODE* pTemp = NULL;
pTemp = m_pHead->next;
m_pHead->next = pTemp->next;
Type rst = pTemp->Item;
delete pTemp;
return rst;
}
容易出现的问题:
1.【struct NODE * next;//前一个节点的地址指针】结构体定义时,下一个节点的指针容易忘记struct符号。
2.在处理入队和出队时容易混淆节点之间的地址传递,导致节点地址丢失。始终要保持操作的节点都有指针指向,才不至于丢失节点。
这里只是基本实现。如果需要更多功能,可以继承这个类,或者自己在此基础添加。因为模板在一些编译器还支持不够好,比如VS2010,或更低版本的编译器。所以不要把模板类的声明和实现分开,否则报错。支持的编译器只要在模板中使用export关键字即可让实现和头文件放在不同的文件中。