链栈

梦里梦外; 2023-02-27 13:34 13阅读 0赞

链栈的基本操作与顺序栈一致，但是实现方法有较大差异  
首先是在成员变量上，链栈中只包含了一个top指针（主要原因是链栈是动态存储的，在程序运行过程中给需要的变量分配内存，而顺序栈是静态的，内存空间已经划分好了）

template<typename T>
    class LinkStack     //链栈类
    {
        
        Node<T>* top;
    public:
        LinkStack();
        ~LinkStack();
        void Push(T Data);
        void Pop();
        T Top();
        bool isEmpty();
    };

其次是Push和Pop操作是通过改变next指针的指向来实现的

template<typename T>
    void LinkStack<T>::Push(T Data)
    {
        
        Node<T>* newnode = new Node<T>;
        newnode->data = Data;
        newnode->next = top;
        top = newnode;
    }

下面是具体的代码

#include<iostream>
    using namespace std;
    
    template<typename T>//节点结构体
    struct Node
    {
        
        T data;
        Node* next;
    };
    
    template<typename T>
    class LinkStack     //链栈类
    {
        
        Node<T>* top;
    public:
        LinkStack();
        ~LinkStack();
        void Push(T Data);
        void Pop();
        T Top();
        bool isEmpty();
    };
    template<typename T>
    LinkStack<T>::LinkStack()
    {
        
        top = NULL;
    }
    template<typename T>
    LinkStack<T>::~LinkStack()
    {
        
        while (top != NULL)
        {
        
            Node<T>* p = top;
            top = top->next;
            delete p;
        }
    }
    template<typename T>
    void LinkStack<T>::Push(T Data)
    {
        
        Node<T>* newnode = new Node<T>;
        newnode->data = Data;
        newnode->next = top;
        top = newnode;
    }
    template<typename T>
    void LinkStack<T>::Pop()
    {
        
        if (top == NULL)
        {
        
            cout << "栈空" << endl;
            return;
        }
        Node<T>* p = top;
        cout << p->data << endl;
        top = top->next;
        delete p;
    }
    template<typename T>
    T LinkStack<T>::Top()
    {
        
        if (top == NULL)
        {
        
            cout << "栈空" << endl;
            return -1;
        }
        return top->data;
    }
    template<typename T>
    bool LinkStack<T>::isEmpty()
    {
        
        if (top == NULL)
            return true;
        else
            return false;
    }
    int main()
    {
        
        LinkStack<int> a;
        a.Push(1);
        a.Push(2);
        a.Push(3);
        a.Pop();
       cout<< a.Top()<<endl;
        if (a.isEmpty())
            cout << "栈为空" << endl;
         else
            cout << "栈不为空" << endl;
    }

最后讲一下顺序栈和链栈的比较  
在空间性能上，两者是相同都是*O*（1）  
空间性能上，顺序栈有元素个数的限制和空间浪费的问题，而链栈没有占满的问题，只有当内存没有可用空间才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，当栈的使用过程中元素个数变化较大是，用链栈是合适的反之，应采用顺序栈。