从栈到虚拟机栈的数据结构

栈这个数据结构，一般在开发中，偶尔会遇到。经常会和队列这一尴尬混淆。

那么什么是栈呢，一个先进后出，后进先出的一个容器。这个容器可以由很多基础容器组成，例如数组，例如双链表。只要是保证天然时间有序的容器，都可以实现栈。

栈的提出是为了什么？这边我的思考其实还是蛮无脑的，先进后出表示的是需要沉底，后进先出表示的是需要上浮。数组天然做到了这个，数组是平躺着的，只需要简单的立起来就可以，那么唯一的区别就是暴露对外的访问方法了。如果说数组是给予了所有的方法，栈则是只暴露部分的方法。数组对于栈而言是个天然的成品，只需要减少就可以。实现起来也很容易，例如数组的添加是从0到N，那么拿的时候从N到0就可以。至于扩容方面只需要进行动态扩容就可以。

import java.util.Arrays;

/**
 * description: Test
 * date: 2020/12/4 15:58
 *
 * @author: SmartCat
 * version: 1.0.0
 */
public class Test<T> {
    static int DEFAULT_NUM=30;

    static int EXPANSION_NUM=2;

    private Object[] array = new Object[DEFAULT_NUM];

    int now = 30;

    private int size=0;

    public int size(){
        return size;
    }

    public void push(T t){
        isFull();
        array[size]=t;
        size++;
    }

    public T pop(){
        T t = (T) array[this.size - 1];
        array[this.size - 1]=null;
        size--;
        return t;
    }

    protected void isFull(){
        while (now*0.8<size){
            Object[] array1 = new Object[now * EXPANSION_NUM];
            System.arraycopy(array,0,array1,0,array.length);
            array = array1;
            now = now * EXPANSION_NUM;
        }
    }

    public T peek() throws Exception {
        if (this.size>1){
            return (T) array[this.size-1];
        }else {
            return (T) new Exception("false");
        }
    }

    @Override
    public String toString(){
        return Arrays.toString(array);
    }

    public static void main(String[] args) throws Exception {
        Test<Integer> test = new Test<>();
        for (int i = 0; i < 100; i++) {
            test.push(i);
        }
        for (int i = 0; i < 30; i++) {
            Integer peek = test.pop();
            System.out.println(peek);
        }
    }
}

　这是使用数组实现的顺序栈，对应还有链表实现的链式栈。链式栈和顺序栈有啥区别。一个是链表天然无限大，无需动态扩容。相对链表实现队列等操作，用链表来实现栈稍微扼杀了一点链表的特性。毕竟栈针对的是尾部的点。FILO

public class Test1<T> {
    private MyNode cur;

    private MyNode head=new MyNode<>(null,null,null);

    private int size=0;

    public void push(T t){
        if (size==0){
            this.cur = head;
        }
        MyNode<T> node = new MyNode<>(t,cur,null);
        cur.next = node;
        cur = node;
        size++;
    }

    public void pop(){
        MyNode prev = cur.prev;
        prev.next=null;
        cur.prev=null;
        cur = prev;
        size--;
    }


    class MyNode<T>{
        private T value;
        private MyNode prev=null;
        private MyNode next=null;

        public MyNode(T value, MyNode prev, MyNode next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

        public MyNode(){}
    }
}

栈在JVM中其实反而是很常见的一个东西，Java虚拟机栈，应该栈的特点是只需要维护当前的栈顶，如果是动态栈那么就再维护下容器的大小就行，如果是固定栈就不需要维护。

在Java虚拟栈中会有两个常见异常，一个是outstackoverflow，一个是outofmemory。如果一个栈是固定大小的，栈里面能存储的栈帧是有限的，如果超过了这个上线就会报出outstackoverflow异常，这个对应的是栈的空间异常，outofmemory对应的是java程序启动一个新线程时，没有足够的空间为改线程分配java栈。因为一个线程必须对应一个Java虚拟机栈。这个我认为是JVM内存区域的异常。

这边我顺带在思考，HotSpot里面的Java虚拟栈是怎么样的一个数据结构，是顺序栈呢还是链式栈呢？

个人认为是顺序栈，首先outstackoverflow异常+JVM的特性。使用链式栈空间要求更大，虽然栈帧不受限制，但是不受控的往往风险更大。但是具体的证据目前还在寻找中。

目前我认为Java虚拟机栈是一个数组实现的顺序栈。