数据结构——链式栈模板类实现

向右看齐 2022-06-07 07:08 225阅读 0赞

**数据结构笔记3.1.3**  
链式栈和前面的顺序栈是栈的两种不同实现形式，其实就是顺序表与链式表，区别在于其实现的方式（数组和指针节点），顺序栈指的是其每个节点的物理存储是连续的，因为是使用数组实现的。而链式栈存储位置则是不连续的，需要指针来穿接。  
但是因为栈的操作单调，相对于单链表更容易实现，单链表相当于是一个泛泛的存储表，其操作更加任意，而像栈、队列这种数据组织结构，其只能在整个表的端进行操作，这也从另一个方面体现出链式栈相对容易实现。  
那为何有顺序表这种总领性的结构，还要建立栈、队列这些子数据结构呢？这就好比是“专门化”与“普遍化”的比较，一般专门化的东西，其在相应问题上的效率会比普遍使用的工具要高，所以，分化后的子结构其存在的意义绝不容小视！最后说一下顺序栈与链式栈的比较，他们都是一种数据组织与操纵方式（DRO），但是在解决不同问题的时候，不同的存储方式实现同样的功能，可能在效率、复杂度、空间利用率等方面都会千差万别，各有千秋！下面贴出代码：  
模板类——链式栈

//数据结构——链式栈的模板类定义 By Zhu Xiuyu 17/10/13
    #include <iostream>
    #include <cassert>
    using namespace std;
    //节点定义
    template<class T>
    struct StackNode {
        T data;                     //栈每个节点的数据域
        StackNode<T> *next;         //栈节点的指针域
        StackNode(T x, StackNode<T> *Node = NULL) : data(x){}
    };
    //模板类定义
    template<class T>
    class LinkedStack {
    public:
        LinkedStack() : top(NULL){}                 //构造函数
        ~LinkedStack();                                //析构函数
        void Push(const T & x);                     //进栈
        bool Pop(T & x);                            //出栈
        bool getTop(T & x) const;                   //读取栈顶元素
        bool isEmpty()const;                        //判断栈是否为NULL
        int getSize() const;                        //求栈的元素的个数
        void makeEmpty();                           //清空栈
        void output(ostream & out);                     //输出函数（此处由重载函数调用）
    private:
        StackNode<T> *top;                          //栈顶指针
    };
    //函数定义
    template<class T>
    void LinkedStack<T>::makeEmpty() {
        //逐个删去链式栈中的元素，直至栈顶指针为空
        StackNode<T> *p;                            //逐个节点释放
        while (top != NULL) {
            p = top;
            top = top->next;
            delete p;
        }
    }
    
    template<class T>
    LinkedStack<T>::~LinkedStack() {
        //析构函数
        makeEmpty();
    }
    
    template<class T>
    bool LinkedStack<T>::isEmpty() const{
        if (NULL == top) {
            return true;
        }
        return false;
    }
    
    template<class T>
    void LinkedStack<T>::Push(const T & x) {
        //将元素x推入栈顶
        StackNode<T> *newNode = new StackNode<T>(x);
        assert(newNode != NULL);                            //内存分配错误的中断处理
        newNode->next = top;
        top = newNode;
    }
    
    template<class T>
    bool LinkedStack<T>::Pop(T & x) {
        //删除栈顶节点，删除的data返回到x当中
        if (isEmpty()) {
            return false;                                   //栈为NULL出栈失败
        }
        StackNode<T> *p = top;                              //标记Top
        top = top->next;                                    //更新栈顶指针
        x = p->data;
        delete p;                                           //释放栈顶元素
        return true;
    }
    
    template<class T>
    bool LinkedStack<T>::getTop(T & x) const {
        //返回栈顶元素的值
        if (isEmpty()) {
            return false;                                   //栈为NULL，读取栈顶失败
        }
        x = top->data;
        return true;
    }
    
    template<class T>
    int LinkedStack<T>::getSize()const {
        StackNode<T> *p = top;
        int len = 0;
        while (p != NULL) {
            p = p->next;
            len++;
        }
        return len;
    }
    
    template<class T>
    void LinkedStack<T>::output(ostream & out) {
        //输出链式栈
        StackNode<T> *p = top;
        while (p != NULL) {
            out << p->data << ' ';
            p = p->next;
        }
    }
    
    template<class T>
    ostream & operator << (ostream & out, LinkedStack<T> & LS) {
        //重载输出运算符
        LS.output(out);                             //避免友元函数在模板class中出现的问题
        cout << endl;
        return out;
    }

测试Main函数

int main()
    {
        //Push and Pop测试
        LinkedStack<int> LS;                        //定义一个链式栈
        LS.Push(1);
        LS.Push(2);
        LS.Push(3);
        LS.Push(4);
        LS.Push(5);
        cout << LS;                                 //用重载函数输出
        int del1, del2;
        LS.Pop(del1);
        LS.Pop(del2);
        cout << LS;
    
        //getSize 和 getTop测试
        int topVal = 0;
        LS.getTop(topVal);
        cout << topVal << endl;
        cout << LS.getSize() << endl;
    
        //判断是否为NULL测试
        if (LS.isEmpty()) {
            cout << "空栈" << endl;
        }
        else {
            cout << "非空栈" << endl;
        }
        LS.makeEmpty();
        if (LS.isEmpty()) {
            cout << "空栈" << endl;
        }
        else {
            cout << "非空栈" << endl;
        }
    
        system("pause");
        return 0;
    }

运行效果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/4b941e136a5c426b92d366a0b3c973ce.png