通过栈实现浏览器的后退前进功能

本文创作灵感来源于极客时间王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。

是什么

什么是栈

栈也是一种线性数据结构，由于实现的方式不同分为：顺序栈和链表栈。
栈是一种操作受限的线性数据结构，只允许在一端进行插入和删除操作，也就是先进后出，后进先出。
为什么
为什么有栈这种数据结构
特定的数据结构是针对特定场景的抽象。虽然栈的功能完全可以只用数组或者链表实现，但是数组与链表暴漏太多的操作接口，操作灵活自然带来更多的不可控因素，出错的概率也更多。
怎么办
怎么学习栈这种数据结构

当某个数据集合只允许在集合的一段进行插入和删除的操作，并且满足先进后出，后进先出的原则，那么这种数据结构就称之为栈。

实现顺序栈

class ArrayStack {
    private String[] stack;//栈数组
    private int count;//栈中元素个数
    private int length;//栈的大小

    //初始化栈
    public  ArrayStack(int length){
        this.stack = new String[length];
        this.count = 0;
        this.length = length;
    }

    //入栈
    public boolean push (String item){
        //判断栈是否满了
        if(count == length){
            return false;
        }else{
            stack[count] = item;
            count++;
            return true;
        }
    }

    //出栈
    public String pop (){
        //判断栈中是否有元素
        if(count == 0){
            return  null;
        }else{
            String item = stack[count];
            count--;
            return  item;
        }
    }
}

实现链表栈

class LinkStack{
    //定义节点
    class Node{
        String data;//数值域
        Node next;//指针域
    }

    //头结点
    private Node headNode;

    //初始化链表栈
    public LinkStack(){
        this.headNode = new Node();
    }

    //入栈
    public boolean push(Node newNode){
        //判断是否为空链表
        if(headNode.next == null){
            headNode.next = newNode;
            return  true;
        }else {
            newNode.next = headNode.next;
            headNode.next = newNode;
            return  true;
        }
    }

    //出栈
    public Node pop(){
        //判断是否为空链表
        if(headNode.next == null){
            return  null;
        }else {
            Node newNode = headNode.next;//获取链表第二个节点
            headNode.next = headNode.next.next;//头结点得指针域指向第三个节点
            newNode.next = null;//释放内存
            return  newNode;
        }
    }
}

栈的动态扩容

对于链表栈来说，没有空间大小的限制，可以一直存储。
对于顺序栈来说，上面的代码中初始化栈的时候，要先指定固定的大小，那么如何实现动态扩容呢。在数组那篇文章中讲到 java 语言中的数组容器 ArryList 类型底层是数组，支持动态扩容。栈的动态扩容和 ArryList 的扩容原理是一致的，重新开辟一个更大的空间，将原数组的元素复制过去。栈的复制，需要一个额外的中转栈，先是入栈后出栈，就完成了栈的复制搬移操作。
对于动态扩容的顺序栈来说，入栈是的最好情况时间复杂度 O(1) ，最坏情况时间复杂度 O(n) 。但是，我们明显知道，大多数情况下入栈的时间复杂度都是 O(1) ，只有栈扩容的时候时间复杂度才是 O(n) ，针对这种情况我们就用到时间复杂的分析方法：摊还分析方法。将最坏情况的时间复杂度均摊到其他情况的时间复杂度上，平均时间复杂度就等于最好情况时间复杂度 O(1) 。
栈在函数中的应用
- 操作系统给没一个线程分配了独立的内存空间，这个内存空间的模型就是栈这种数据结构。当程序执行的试试，我们会把主函数压入栈底，当调动其他函数的时候，我们会把被调用的函数当做临时变量(栈帧)压入栈中，当调用函数执行完毕，对该临时变量进行出栈，这就保证了我们函数调用的准确性。
  栈在表达式中的应用
编译器是利用栈实现计算表达式的值得，下面我们以简单的加减乘除四则运算分析栈如何计算表达式的值。
两个栈，一个栈用来存储操作数记做操作数栈，一个栈用来存储运算符记做运算符栈。对表达式从左到右开始读取，遇见操作数，就放进操作数栈。当遇到运算符的时候，就与运算符栈的栈顶元素对比：

如果当前运算符的优先级大于栈顶的运算符：直接放入运算符栈，继续往下读。

如果当前运算符的优先级等于或者小鱼栈顶的运算符：直接从操作数栈中读取两个元素进行计算，并将结果放入操作数栈中。

栈在括号匹配中的应用
简化问题，假设只有三种括号：圆括号()，花括号{}，大括号[]。
遇到左括号，就入栈，遇到右括号就从栈顶取出一个元素，比较两个括号是否匹配。如果匹配，证明表达式中括号用法正确，不匹配就证明用法不正确。直到对所有的括号检查过一遍后，看看栈中是否还有元素，如果有那就证明表达式中括号用法不正确，反之则是正确。
如何用栈实现浏览器的前进后退
第一个栈用来存储不断开发的网页，没打开一个新的网页，就往栈中压入一个元素。
第二个栈用来存储浏览器点击后退功能时，第一个栈出栈的元素，直接入栈到第二个栈。
如果浏览器点击前进，则取出第二个栈的栈顶元素，压入第一个栈。
如果浏览器后退后，有点击了新的网页，则第二个栈中的元素全部出栈。
总结
初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉

通过栈实现浏览器的后退前进功能

是什么

什么是栈

为什么

为什么有栈这种数据结构

怎么办

怎么学习栈这种数据结构

实现顺序栈

实现链表栈

栈的动态扩容

栈在函数中的应用

栈在表达式中的应用

栈在括号匹配中的应用

如何用栈实现浏览器的前进后退

总结