非循环链队列

溯影

《数据结构C++描述》 清华大学出版社    任燕编著
小弟还是改遍了程序，使之可以运行，同时还是重载了输出运算符，
便于输出，共勉

#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include <assert.h>
using namespace std;

template <typename elemtype>
class LinkQueue{
public:
        class LinkNode{
        public:
                elemtype data;
                LinkNode *next;
        };
        typedef LinkNode* NodePointer;

        //非循环链队列置空
        void clear();

        //出队列(删除头节点)
        bool deQueue(elemtype &e);

        //进队列
        void enQueue(elemtype e);

        //读取头节点的数据域
        bool getFront(elemtype &e);

        //判断是否为空
        bool isEmpty();

        //求结点个数
        int getLength();

        //重载赋值运算符
        LinkQueue operator=(LinkQueue right);

        //构造函数
        LinkQueue();

        //析构函数
        virtual ~LinkQueue();

        //拷贝初始化构造函数
        LinkQueue(LinkQueue &other);

        //重载输出函数
        template <typename out_put>
        friend ostream& operator<<(ostream& out, LinkQueue<out_put> &other);

protected:
        NodePointer front;//对头指针
        NodePointer rear;//队尾指针
};

template <typename elemtype>
void LinkQueue<elemtype>::clear(){
        NodePointer q;
        NodePointer p = front;
        while (p){
                q = p;
                p = p->next;
                delete p;
        }
        front = rear = NULL;
}

//出队列
template <typename elemtype>
bool LinkQueue<elemtype>::deQueue(elemtype &e){
        if (!front){
                return false;
        }
        NodePointer s = front;
        e = s->data;
        front = front->next;
        delete s;

        if (!front){
                rear = NULL;//如果该队列未空，那么尾指针也要设置为空
        }

        return true;
}


//进队列
template <typename elemtype>
void LinkQueue<elemtype>::enQueue(elemtype e){
        NodePointer s;
        s = new LinkNode;
        assert(s != 0);
        s->data = e;
        s->next = NULL;
        if (!front){
                front = rear = s;
        }
        else{
                rear->next = s;
                rear = s;
        }
}

template <typename elemtype>
bool LinkQueue<elemtype>::getFront(elemtype &e){
        if (!front){
                return false;
        }
        e = front->data;
        return true;
}

template <typename elemtype>
bool LinkQueue<elemtype>::isEmpty(){
        return !front ? true : false;
}

template <typename elemtype>
int LinkQueue<elemtype>::getLength(){
        int length = 0;
        NodePointer p = front;

        while (p){
                length++;
                p = p->next;
        }
        return length;
}

//重载赋值运算符
template <typename elemtype>
LinkQueue<elemtype> LinkQueue<elemtype>::operator=(LinkQueue<elemtype> right){
        NodePointer s;
        NodePointer rp = right.front;

        if (this != &right){
                clear();
                while (rp){
                        s = new LinkNode;
                        assert(s != 0);
                        s->data = rp->data;
                        s->next = NULL;

                        if (!front){
                                front = rear = s;
                        }
                        else{
                                rear->next = s;
                                rear = s;
                        }
                        rp = rp->next;
                }
        }
        return *this;//返回对象
}

template <typename elemtype>
LinkQueue<elemtype>::LinkQueue(){
        front = rear = NULL;
}

template <typename elemtype>
LinkQueue<elemtype>::~LinkQueue(){
        clear();
        cout << "链队列清除完毕" << endl;
}

template <typename elemtype>
LinkQueue<elemtype>::LinkQueue(LinkQueue<elemtype> &other){
        NodePointer s;
        NodePointer op = other.front;

        rear = front = NULL;//当前队列置空，准备接受other的初始化
        while (op){
                s = new LinkNode;
                assert(s != 0);

                s->data = op->data;
                s->next = NULL;

                if (!front){
                        front = rear = s;
                }
                else{
                        rear->next = s;
                        rear = s;
                }
                op = op->next;
        }
}


//重载输出函数
template <typename out_put>
ostream& operator<<(ostream& out, LinkQueue<out_put> &other){
        while (other.front){
                out << other.front->data << "\t";
                other.front = other.front->next;
        }
        return out;
}


int main(void){
        LinkQueue<int> s1;
        for (int i = 1; i <= 10; i++){
                s1.enQueue(i);
        }

        cout << "链队列为:" << endl;
        cout << s1 << endl;
        return 0;
}