重温数据结构-栈

做开发的同学对栈和队列一定不会陌生，但是大家有没有发现我们在日常工作中却很少会用到堆栈，队列倒是在不少场合会用到，今天我就来给大家先讲讲栈。

栈的介绍

栈给大家的印象就是先进后出，栈其实就是一种操作受限的线性表，只允许在一端插入和删除操作，并且入栈和出栈的时间复杂度都是O(1)。栈的功能确实很单一，并且能够被数组和链表进行替代，但是数组和链表都存在很多其他的复杂操作，虽然操作上灵活自由了，但是同时也造成了很容易出错。栈的对外接口就只有入栈和出栈，操作极其简单，这就保证了操作的简单化，自然也就不容易出错。对于栈主要有两种实现方法，一种是基于数组的，一种是基于链表的，这两种数据结构实现的栈都能够做到入栈和出栈的时间复杂度为O(1).

栈的使用场景

下面介绍下大家都比较困惑的问题，栈到底在哪些场景下使用。

JVM函数调用

JVM中函数栈的调用就是栈的一个典型应用场景。JVM给每个线程都分配了一个独立的内存空间，这块内存空间被称为线程栈，用来存储函数调用时的临时变量，每进入一个函数，就会将临时变量封装成一个栈桢，并将该函数栈桢入线程栈，当被调用函数执行完成后，这个函数对应的栈桢就做出栈操作，并将函数结果返回，这样多层函数调用，先将每个函数的栈桢入栈，每执行完一个函数做出栈操作，并把结果返回给下个栈桢，最后全部完成出栈后则函数也得到了最终结果。

编译器语法分析

学过计算机编译原理的同学应该知道，编译器在进行语言的语法分析的时候，并不是简单的顺序的一个字节一个字节的读取进行判断特征码，而也是使用到了堆栈，例如判断一句复杂的表达式格式语法是否正确

if((a.sum()/b.count())){
    ....
}

如果顺序判断括号是否匹配则很困难，这时编译器就是将所有左括号和变量识别出后分别入不同类别的栈，然后再匹配到右括号后再将左括号做出栈操作，如果最后栈不为空则说明语法有问题。在编译器语法分析的过程中还有很多用到堆栈的地方。

栈的实现

基于数组实现的栈

基于数组实现的堆栈在入栈和出栈的性能上是最好的，而且结构也很简单，只需要维护一个定长的数组就可以了，入栈和出栈都通过栈顶下标来操作。

public class ArrayStack {

    private String[] datas;
    private int head;
    private int count;

    public ArrayStack(int size){
        datas = new String[size];
        head = 0;
        count =0;
    }

    public boolean push(String data){
        if(count==datas.length){
            return false;
        }else if(count==0){
            datas[head] = data;
            count++;
            return true;
        }else{
            datas[++head]=data;
            count++;
            return true;
        }
    }

    public String pop(){
        if(count==0){
            return null;
        }else{
            String data = datas[head--];
            count--;
            return data;
        }
    }
}

基于链表实现的栈

基于链表同样也可以实现栈的数据结构，因为为了链表插入和删除的便利性，需要设计一个双向链表来满足要求。

public class LinkedListStack {

    private Node head;
    private int count;
    private int size;

    public LinkedListStack(int size){
        this.size = size;
        head = null;
        count = 0;
    }

    public boolean push(String data){
        if(count==0){
            head = new Node(data, null, null);
            count++;
            return true;
        }else if(count==size){
            return false;
        }else{
            head.next = new Node(data, null, head);
            head = head.next;
            count++;
            return true;
        }
    }

    public Node pop(){
        if(count==0){
            return null;
        }else{
            Node data = head;
            head = head.pre;
            count--;
            return data;
        }
    }

    public class Node {
        public String data;
        public Node next;
        public Node pre;

        public Node(String data, Node next,Node pre){
            this.data = data;
            this.next = next;
            this.pre = pre;
        }
    }
}

支持动态扩容的栈

其实栈的扩容非常简单，对于基于数组实现的栈结构来说，是需要重新创建一个新的数组空间，将已满数组中的数据复制到新的数组中，这样就完成了扩容，需要做一次数据迁移，对于基于链表结构实现的栈则可以无限自动扩容。

下面的代码是基于数组的动态扩容的栈结构，在push的时候需要判断如果栈满了，则进行新数据创建和数据迁移。

public class DynamicArrayStack {
    private String[] datas;
    private int head;
    private int count;

    public DynamicArrayStack(int size){
        datas = new String[size];
        head = 0;
        count =0;
    }

    public boolean push(String data){
        if(count==datas.length){
            String[] oldDatas = datas;
            datas = new String[oldDatas.length*2];
            //将旧数据迁移到新数组中
            for(int i=0;i<oldDatas.length;i++){
                datas[i] = oldDatas[i];
            }
            datas[++head] = data;
            count++;
            return true;
        }else if(count==0){
            datas[head] = data;
            count++;
            return true;
        }else{
            datas[++head]=data;
            count++;
            return true;
        }
    }

    public String pop(){
        if(count==0){
            return null;
        }else{
            String data = datas[head--];
            count--;
            return data;
        }
    }
}

总结

上面介绍了栈的使用场景和实现方式，从这几种实现方式，我们也能发现同样是栈结构在基于不同的底层数据结构实现的的方式是有差异的，这也就导致了在不同场合使用不同实现方式的栈会有不同的效果，如果内存空间紧张则使用基于数组的栈比较好，如果是经常会造成扩容操作，则使用链式结构的栈更好。

所以总的来说数据结构的选择和使用场景是非常相关的，每一种结构包括底层实现方式在不同的使用场景都有不同的使用效果，希望大家慢慢体会。