基本数据结构之栈(stack)

约定不等于承诺〃 2022-03-30 10:56 315阅读 0赞

栈（stack）是限制插入和删除只能在一个位置上进行的线性表，该位置在表的末端，叫做栈顶。添加元素只能在尾节点后添加，删除元素只能删除尾节点，查看节点也只能查看尾节点。添加、删除、查看依次为入栈（push）、出栈（pop）、栈顶节点（top）。形象的说，栈是一个先进后出（LIFO）表，先进去的节点要等到后边进去的节点出来才能出来。

![1361160170_1731.png][]

如图1，是一个栈的形象图，top指针指向的是栈顶节点，所以我们可以通过top访问到2节点，但是0和1节点由于先于2进入这个表，所以是不可见的。如果把0节点当做头节点，2节点当做尾节点，那么栈限制了访问权限，只可以访问尾节点。

![1361160170_7098.png][]

如图2，当添加一个节点3的时候，只能在栈顶节点，也就是尾节点后添加，这样3节点变成了栈顶，2节点变成了不可见节点，访问的时候只能访问到3节点。入栈时限制了插入地址，只能在栈顶添加节点。

![1361160170_7674.png][]

当我们执行出栈的命令时，图2的栈顶元素是3节点，删除的时候只能允许删除栈顶的元素，这样子3节点被删除，top指向删除后的栈顶2节点，如图3所示。

栈有两种是实现结构，一种是顺序存储结构，也就是利用数组实现，一种是链式存储结构，可以用单链表实现。数组实现栈很简单，用一个下标标记top来表示栈顶，top==-1时，栈空，top==0时，表示栈里只有一个元素，通过访问top为下标的数组元素即可。出栈top自减，入栈top自加就OK了。

单链表实现栈要比单链表的实现简单点。我们通过在表的尾端插入来实现push，通过删除尾节点来实现pop，获取尾节点的元素来表示top。我修改了链表那一章的单链表代码，把头节点当做栈顶节点，实现了一个简单的栈模板，仅供学习所用。

代码下载：[点击打开链接][Link 1]

代码如下：

template<class T>
    class stackNode
    {
        public:
        stackNode():next(NULL){}
        T data;//值
        stackNode* next;//指向下一个节点的指针
    };
    template<class T>
    class mystack
    {
        private:
        unsigned int stacklength;
        stackNode<T>* node;//临时节点
        stackNode<T>* headnode;//尾结点
        public:
            mystack();//初始化
            unsigned int length();//栈元素的个数
            void push(T x);//入栈
            bool isEmpty();//判断栈是否为空
            void pop();//出栈
            T top();//获得栈顶元素
            void clear();//清空栈
    
    };
    template<class T>
    mystack<T>::mystack()
    {
        node=NULL;
        headnode=NULL;
        stacklength=0;
    }
    template<class T>
    inline unsigned int mystack<T>::length(){return stacklength;}
    template<class T>
    void  mystack<T>::push(T x)
    {
        node=new stackNode<T>();
        node->data=x;
        node->next=headnode;//把node变成头节点
        headnode=node;
        ++stacklength;
    }
    template<class T>
    bool  mystack<T>::isEmpty()
    {
        return stacklength==0;
    }
    template<class T>
    void  mystack<T>::pop()
    {
        if(isEmpty()) return;
        node=headnode;
        headnode=headnode->next;//头节点变成它的下一个节点
        delete(node);//删除头节点
        --stacklength;
    }
    template<class T>
    T  mystack<T>::top()
    {
        if(!isEmpty())
        return headnode->data;
    }
    template<class T>
    void  mystack<T>::clear()
    {
        while(headnode!=NULL)
        {
            node=headnode;
            headnode=headnode->next;
            delete(node);
        }
        node=NULL;
        headnode=NULL;
        stacklength=0;
    }

很清楚，除了clear函数外，所有的方法的时间复杂度都是O(1)。这种实现方式的缺点在于对new和delete的调用的开销是昂贵的，所以采用数组的方式实现会更好一点。

**栈的应用**

使用栈的时候一般不用自己重新去写，因为STL给我们实现了一个很安全的栈，可以放心去使用。也可以用数组模拟一个，很简单。

编译器调用函数就用了栈结构，当第一个函数还没执行完毕，调用第二个函数的时候，编译器就会把第一个函数压栈，第二个函数调用完毕的时候，就会取栈顶函数，也就是第一个函数继续执行。

[1361160170_1731.png]: https://img-my.csdn.net/uploads/201302/18/1361160170_1731.png
[1361160170_7098.png]: https://img-my.csdn.net/uploads/201302/18/1361160170_7098.png
[1361160170_7674.png]: https://img-my.csdn.net/uploads/201302/18/1361160170_7674.png
[Link 1]: http://download.csdn.net/detail/laoylhuli/5070423