用C++模块实现队列

队列这种数据结构与栈一样，是一个工具性的数据结构，通常被其它复杂数据结构所使用。比如实现二叉树的遍历的非递归算法(层次遍历)。下面就用C++模板实现队列数据结构的一个较完整代码！队列可以以用数组，也可以用链表实现，这里只用双向链表实现这一数据结构。

//Queue.h
//双链表队列数据结构C++模块的实现
//理论知识参考《数据结构（C语言版）--严慰明》
#ifndef _QUEUE_H_
#define _QUEUE_H_

namespace _QUEUE_
{
    //队列中的数据元素
    template <typename T>
    class QueueNode
    {
    public:
        QueueNode()
        {
            this->mElement    = 0;
            this->mpNext = this->mpPrev    = NULL;
        }
        T                mElement;
        QueueNode<T>*    mpNext;
        QueueNode<T>* mpPrev;
    };

    template <typename T>
    class Queue
    {
    public:
        Queue()
        {
            QueueNode<T> * pNode = new QueueNode<T>;
            pNode->mElement = T(-1);
            pNode->mpNext = pNode->mpPrev = NULL;
            this->mpHead = this->mpTail = pNode;
        }

        ~Queue()
        {
            this->clear();
            delete this->mpHead;
            this->mpHead = this->mpTail = NULL;
        }

        bool insert(T element);
        T    front();
        T    back();
        bool isEmpty(void);
        bool clear(void);
        int size();

        friend ostream& operator<< <>(ostream& ostr,const Queue<T>& q);
    private:
        QueueNode<T>* mpHead;
        QueueNode<T>* mpTail;
    };

    template <typename T>
    bool Queue<T>::insert(T element)
    {
        QueueNode<T> * pNode = new QueueNode<T>;
        if (pNode == NULL)    return false;
        pNode->mElement    = element;

        this->mpTail->mpNext = pNode;
        pNode->mpPrev = this->mpTail;
        this->mpTail = this->mpTail->mpNext;

        return true;
    }

    template <typename T>
    T    Queue<T>::front()
    {
        T element = T();
        QueueNode<T>* pNode = NULL;
        if (!this->isEmpty())
        {
            pNode = this->mpHead->mpNext;
            element = pNode->mElement;
            this->mpHead ->mpNext = pNode->mpNext;
            if (pNode->mpNext)
                pNode->mpNext->mpPrev = this->mpHead;
            if (pNode == this->mpTail)
                this->mpTail = this->mpHead;
            delete pNode;
        }
        return element;
    }

    template <typename T>
    T    Queue<T>::back()
    {
        T element = T();
        QueueNode<T>* pNode = NULL;
        if (!this->isEmpty())
        {
            pNode = this->mpTail;
            element = pNode->mElement;
            this->mpTail = this->mpTail->mpPrev;
            this->mpTail->mpNext = NULL;
            delete pNode;
        }
        return element;
    }

    template <typename T>
    bool Queue<T>::isEmpty(void)
    {
        return (this->mpTail == this->mpHead);
    }

    template <typename T>
    bool Queue<T>::clear(void)
    {
        while (!this->isEmpty())
            this->back();
        return true;
    }

    template <typename T>
    int Queue<T>::size()
    {
        int iCount = 0;
        if (!this->isEmpty())
        {
            QueueNode<T>* pNode = this->mpTail;
            while (pNode != this->mpHead)
            {
                iCount++;
                pNode = pNode->mpPrev;
            }
        }
        return iCount;
    }

    template <typename T>
    ostream& operator<< <>(ostream& ostr,const Queue<T>& q)
    {
        QueueNode<T>* pNode = q.mpHead->mpNext;
        while (pNode != NULL)
        {
            ostr << pNode->mElement << ",";
            pNode = pNode->mpNext;
        }
        return ostr;
    }
}
#endif

以上就是队列数据结构的实现。