第10节 链式队列

/* 主题: 链式队列
* 作者: chinazhangjie(邮箱:[email protected])
* 开发语言: C++
* 开发环境: Microsoft Visual Studio 2008
* 日期: 2010.09.12
*/
template <class T>
class LinkedQueue {
    typedef     T                ValueType;
    typedef unsigned int    Size;
    struct Node;

public:
    // 构造函数
    LinkedQueue() {
        __initQueue();
    }
    // 拷贝构造函数
    LinkedQueue(LinkedQueue& lq) {
        __initQueue();
        __copy(lq);
    } 
    // 析构函数
    ~LinkedQueue() {
        __destroyQueue();
    }
    // 获得长度
    Size length() const {
        return m_len;
    }
    // 如果队列不空，返回队头元素
    ValueType getHead() const {
        if (m_len == 0) {
            throw std::out_of_range("getHead out_of_range");
        }
        return m_pfront->m_pnext->m_data;
    }
    // 清空队列
    void clear() {
        __clearQueue();
    }
    // 判空
    bool empty() const {
        return m_len == 0;
    }
    // 入队
    void enQueue(ValueType data) {
        Node* pnode = new Node(data);
        if (pnode == 0)
            throw std::bad_alloc("enQueue bad_alloc");
        if (length() == 0) {
            m_pfront->m_pnext = pnode;
            m_prear = pnode;
        }
        else {
            pnode->m_pnext = m_pfront->m_pnext;
            m_pfront->m_pnext = pnode;
        }
        ++ m_len;
    }
    // 出队
    ValueType deQueue() {
        if (length() == 0) {
            throw std::out_of_range("deQueue out_of_range");
        }
        ValueType data = m_prear->m_data;
        if (length() == 1) {
            __clearQueue();
        }
        else {
            Node* delTmp = m_prear;
            Node* tmp = m_pfront;
            while (tmp->m_pnext != delTmp) {
                tmp = tmp->m_pnext;
            }
            m_prear = tmp;
            m_prear->m_pnext = 0;
            delete delTmp;
        }
        -- m_len;
        return data;
    }
    // 重载赋值运算符
    LinkedQueue& operator = (LinkedQueue& rhs) {
        if (this == &rhs)
            return *this;
        __clearQueue();
        __copy(rhs);
        return *this;
    } 

    // 输出所有元素，仅为调试之用
    void display() const {
        if (length() == 0)
            return ;
        Node* tmp = m_pfront->m_pnext;
        while (tmp != 0) {
            std::cout << tmp->m_data << " " ;
            tmp = tmp->m_pnext;
        }
        std::cout << std::endl;
    }

private:
    // 构造一个空队列
    void __initQueue() {
        m_pfront = new Node();
        if (m_pfront == 0)
            throw std::bad_alloc("__initQueue bad_alloc");
        m_prear = m_pfront->m_pnext;
        m_len = 0;
    }
    // 清空队列
    void __clearQueue() {
        if (length() == 0)
            return ;
        else {
            Node* tmp = m_pfront->m_pnext;
            while (tmp != 0) {
                Node* delTmp = tmp;
                tmp = tmp->m_pnext;
                delete delTmp;
            }
            m_pfront->m_pnext = 0;
            m_prear = 0;
            m_len = 0;
        }
    }
    // 销毁队列
    void __destroyQueue() {
        __clearQueue();
        delete m_pfront;
    }
    // 复制
    void __copy(LinkedQueue& lq) {
        int i = lq.length()-1;
        
        while (i >= 0) {
            this->enQueue(lq.__at(i));
            -- i;
        }
    }
    // 
    ValueType __at(Size s) {
        Size i = 0;
        Node* tmp = m_pfront->m_pnext;
        while (i < s) {
            tmp = tmp->m_pnext;
            ++ i;
        }
        return tmp->m_data;
    }

private:
    Node*    m_pfront;    // 队头指针
    Node*    m_prear;    // 队尾指针
    Size    m_len;        // 队列长度

private:
    // 节点类
    struct Node {
        ValueType    m_data;
        Node*        m_pnext;    
        Node(ValueType data = T()) 
            : m_data(data),m_pnext(0)
        {}
    };
};