以下是实现基于模板的队列。是基于单链表的结构。采用尾插法实现。

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关键字即可让实现和头文件放在不同的文件中。