栈

栈 【转载】

原文；https://www.jianshu.com/p/68b1756ee5e5

---

栈的基本结构

后进先出，先进后出，这就是典型的栈结构

image

从栈的操作特性上来看，栈是一种"操作受限"的线性表，只允许在一端插入和删除数据。
从功能上来说，数组或链表可以代替栈，但特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上的却灵活自由，但使用就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特定，就应该首选栈这种数据结构

实现一个栈

栈主要包括两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
栈既可以用数组来实现，也可以用链表来实现。

用数组实现的栈，我们叫做顺序栈
用链表实现的栈，我们叫做链式栈

数组实现顺序栈:

    // 基于数组实现的顺序栈
    public class ArrayStack {
        // 数组
        private String[] items;
        // 栈中元素个数
        private int count;
        // 栈的大小
        private int n;

        // 初始化数组，申请一个大小为n的数组空间
        public ArrayStack(int n) {
            this.items = new String[n];
            this.n = n;
            this.count = 0;
        }

        // 入栈操作
        public boolean push(String item) {
            // 数组空间不够了，直接返回false,入栈失败
            if( count == n ){
                return false;
            }
            // 将item 放到下标为count 的位置，并且count++
            items[count++] = item;
            return true;
        }

        // 出栈操作
        public String pop() {
            // 栈为空，则直接返回null
            if(count == 0){
                return null;
            }
            // 返回下标为count - 1 的数组元素,并且栈中元素个数 count - 1
            String tmp = items[count - 1];
            count --;
            return tmp;
        }
    }

链式栈的实现
参考: https://www.jianshu.com/p/b913262896f5

    public class LinkedStack {
        private Item dummy = new Item("dummy");
        // 作为栈中最后一个节点
        private Item head;

        LinkedStack() {
            head = dummy;
        }

        boolean pop() {
            if(dummy.next == null){
                return false
            } else {
                head = head.before;
                head.next = null;
                return true;
            }
        }

        boolean push(String val) {
            Item.item = new Item(val);
            item.next = null;
            item.before = head;
            item.next = item;
            head = head.next;
            return true
        }

        class Item {
            String val;
            // 使用双向链表来处理pop
            Item next;
            Item before;

            Item(String val) {
                this.val = val;
            }
        }
    }

不管是顺序栈还是链式栈，存储数据只需要一个大小为n的存储空间。
在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)
空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间
不管是顺序栈还是链式栈，入栈，出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)

支持动态扩容的顺序栈

上面基于数组实现的栈，当栈满之后，就无法再往栈里添加数据了，尽管链式栈的大小不受限，但要存储next指针，内存消耗相对比较多

要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中：

image

出栈的时间复杂度度是O(1)，因为出栈操作不会涉及内存的重新申请和数据的搬移

对于入栈的操作来说，最好情况时间复杂度是O(1)，最坏情况时间复杂度是O(n)。当栈中有空闲空间时，入栈操作的仅1次赋值操作。但当空间不够时，就需要重新申请内存和数据搬移。

对于平均情况下的时间复杂度，可以采用摊还分析法

假设：

• 栈空间不够时，重新申请一个原来大小两倍的数组；
• 只有入栈操作没有出栈操作
• 入栈操作均为simple-push操作，时间复杂度为O(1)。

如果当前栈大小为k已满，入栈时就要重新申请2倍大小的内存，并且做k个数据的搬移操作，然后再入栈。但接下来的k - 1次入栈操作都只需要simple-push操作就可以完成:

image

这k次入栈操作，总共涉及了k个数据的搬移，以及k次simple-push操作。将k个数据搬移均摊到到k次入栈操作，那每个入栈操作只需要一个数据搬移和一个simple-push操作。一次类推，入栈操作的均摊时间复杂度就为O(1)

均摊时间复杂度一般都等于最好情况时间复杂度因为在大部分情况下，入栈操作的时间复杂度都是O(1)，只有在个别时刻才会退化为O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近O(1)。

栈在软件工程中的实际应用

函数调用栈

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成"栈"这种结构，用来存储函数调用时临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈:

    int main() {
        int a = 1;
        int ret = 0;
        int res = 0;
        ret = add(3,5);
        res = a + ret;
        printf("%d",res);
        return 0;
    }
    int add((int x,int y){
        int sum = 0;
        sum = x + y;
        return sum;
    })

main() 函数调用了add() 函数，获取计算结果，并且与临时变量 a 相加，最后打印 res 的值。

下图表示在执行add()函数时，函数调用栈出栈，入栈的情况。

image

栈实现表达式求值

编辑器如何利用栈来实现表达式求值? 比如：34 + 13 * 9 + 44 - 12 / 3
需要两个栈来实现：一个栈保存操作数，另一个栈保存运算符

从左向右遍历表达式，遇到数字就压入操作数栈；

遇到运算符，就与运算符的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

下图时3 + 5 * 8 - 6这个表达式的计算过程：

image

栈实现括号匹配

借助栈来检查表达式中的括号是否匹配：

假设表达式中只包含三种括号，圆括号()， 方括号[]，和花括号{}, 并且它们可以随意嵌套。比如{ [ () ] } [ { ( ) } ( [ ] ) ]等均为合法格式，而{ [ } ( ) ] 或 [ ( { ) ]为不合法的格式。对于一个包含三种括号的表达式字符串，如何检查他是否合法呢?

"(" 跟 ")" 匹配,"["跟"]"匹配，"{"跟"}"匹配

使用一个栈即可实现：

从左到右依次扫描字符串，遇到左括号则将其压入栈中；

当扫描右括号时，从栈顶取出一个左括号。如果能匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能匹配的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

实现浏览器的前进和后退功能

依次访问完一串页面 a-b-c，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。后退到页面 a ,点击前进按钮，就可以重新查看页面 b 和 c 。但是，如果后退到页面 b 后，点击了新的页面 d ，那就无法再通过前进，后退功能查看页面c。如何实现这个功能呢?

使用两个栈 X 和 Y 即可实现:

栈X中的栈顶数据表示当前访问的页面

打开页面时将数据压入栈X，并清空栈Y。

当点击后退按钮时，取出栈X数据并放入栈Y中。

当点击前进按钮时，取出栈Y数据放入栈X中。

当栈X中仅剩1个数据时，那就说明没有页面可以继续后退浏览了。

当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。

流程示例: 顺序查看 a, b, c三个页面，就依次把a, b, c压入栈X：

image

点击后退按钮，从页面c后退到页面a之后，就依次把c和b从栈X中弹出，并且依次放入到栈Y：

image

有点击前进按钮回到b页面，就把b从栈Y中出栈，再放入X栈中：

image

通过页面b访问新页面d，将d放入栈X中，并清空栈Y：

image

总之，后退时将页面从X移到Y，前进则将页面从Y以到X，访问新页面时，则将新页面压入X，并清空Y

三种操作都是取X的栈顶元素显示

---

以上