链栈

溯影

《数据结构C++语言描述》清华大学出版社  任燕编著

小弟改遍了一些程序使之可以作为程序来运行
同时小弟还是老样子重载输出运算符，便于输出链栈每个结点的数据域中的数据
程序小弟调试过没有错

还行大神赐教！！！

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

template <typename elemtype>
class LinkStack{
public:
        class LinkNode{
        public:
                elemtype data;
                LinkNode *next;
        };

        typedef LinkNode* NodePointer;

        //把链栈置空
        void clear();

        //求链栈中结点的个数
        int getLength();

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

        //读取栈顶结点的数据域
        bool getTop(elemtype &e);

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

        //弹出栈顶结点
        bool pop(elemtype &e);

        //在栈顶压入一个数据域为e的结点
        void push(elemtype e);

        LinkStack();//链栈构造函数

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

        //链栈拷贝构造函数
        LinkStack(LinkStack &other);

        template <typename out_put>
        friend ostream& operator<<(ostream& out, LinkStack<out_put> other);

protected:
        NodePointer top;//链栈栈顶指针
};

template <typename elemtype>
void LinkStack<elemtype>::clear(){
        NodePointer s;

        while (top){
                s = top;
                top = top->next;
                delete s;
        }
        top = NULL;
}

template <typename elemtype>
int LinkStack<elemtype>::getLength(){
        int length = 0;
        NodePointer p = this->top;

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

template <typename elemtype>
bool LinkStack<elemtype>::getTop(elemtype &e){
        if (!top){
                return false;
        }
        else{
                e = top->data;
                return true;
        }
}

//判断链栈是否为空
template <typename elemtype>
bool LinkStack<elemtype>::isEmpty(){
        return top ? false : true;
}

//重载赋值运算符
template <typename elemtype>
LinkStack<elemtype> LinkStack<elemtype>::operator=(LinkStack<elemtype> right){
        NodePointer p;//左边链栈当前处理结点的指针

        NodePointer rp = right.top;
        NodePointer s;//预指向左边链栈新节点的指针

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

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

//弹栈
template <typename elemtype>
bool LinkStack<elemtype>::pop(elemtype &e){
        NodePointer s = top;
        if (!top){
                return false;
        }
        else{
                e = top->data;
                top = top->next;
                delete s;
        }
        return true;
}


//压栈
template <typename elemtype>
void LinkStack<elemtype>::push(elemtype e){
        NodePointer s;

        s = new LinkNode;
        assert(s != 0);
        s->data = e;
        s->next = top;
        top = s;
}

template <typename elemtype>
LinkStack<elemtype>::LinkStack(){
        top = NULL;
}

template <typename elemtype>
LinkStack<elemtype>::~LinkStack(){
        clear();
        cout << "清理栈完毕" << endl;
}

//链栈拷贝构造函数
template <typename elemtype>
LinkStack<elemtype>::LinkStack(LinkStack<elemtype> &other){
        NodePointer p;
        NodePointer op = other.top;

        NodePointer s;

        top = p = NULL;

        while (op){//这些代码你懂的
                s = new LinkNode;
                assert(s != 0);
                s->data = op->data;
                if (!top){
                        top = s;
                        cout << "第一个结点插入中" << endl;
                }
                else{
                        p->next = s;
                        cout << "结点插入中" << endl;
                }
                p = s;
                op = op->next;
        }
        if (p){
                p->next = NULL;//链栈栈底结点的指针置空
        }
}

//输出运算符重载
template <typename out_put>
ostream& operator<<(ostream& out, LinkStack<out_put> other){
        LinkStack<out_put>::NodePointer s = other.top;
        while (s){
                out << "值:" << s->data << endl;
                s = s->next;
        }
        return out;
}

int main(void){
        LinkStack<int> s1;
        for (int i = 1; i < 11; i++){
                s1.push(i);//测试压栈成员函数
        }
        cout << "链栈插入完毕:" << endl;
        cout << "链栈为:" << endl;
        cout << s1 << endl;//测试重载输出运算符
        cout << "弹栈:" << endl;
        for (int i = 1; i < 11; i++){
                int e;
                if (s1.pop(e)){//测试弹栈成员函数
                        cout << e << endl;
                }
        }

        LinkStack<int> s2;
        for (int i = 1; i <= 5; i++){
                s2.push(i);
        }

        s1 = s2;//测试赋值运算符的重载

        cout << "s1为:" << endl;
        cout << s1;


        return 0;
}

运行结果:
链栈插入完毕:
链栈为:
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
值:10
值:9
值:8
值:7
值:6
值:5
值:4
值:3
值:2
值:1
清理栈完毕

弹栈:
10
9
8
7
6
5
4
3
2
1
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
清理栈完毕
清理栈完毕
s1为:
第一个结点插入中
结点插入中
结点插入中
结点插入中
结点插入中
值:5
值:4
值:3
值:2
值:1
清理栈完毕
清理栈完毕
清理栈完毕
请按任意键继续. . .