栈这个数据结构,一般在开发中,偶尔会遇到。经常会和队列这一尴尬混淆。
那么什么是栈呢,一个先进后出,后进先出的一个容器。这个容器可以由很多基础容器组成,例如数组,例如双链表。只要是保证天然时间有序的容器,都可以实现栈。
栈的提出是为了什么?这边我的思考其实还是蛮无脑的,先进后出表示的是需要沉底,后进先出表示的是需要上浮。数组天然做到了 这个,数组是平躺着的,只需要简单的立起来就可以,那么唯一的区别就是暴露对外的访问方法了。如果说数组是给予了所有的方法,栈则是只暴露部分的方法。数组对于栈而言是个天然的成品,只需要减少就可以。实现起来也很容易,例如数组的添加是从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虚拟栈中会有两个常见异常,一个是out*,一个是outofmemory。如果一个栈是固定大小的,栈里面能存储的栈帧是有限的,如果超过了这个上线就会报出out*异常,这个对应的是栈的空间异常,outofmemory对应的是java程序启动一个新线程时,没有足够的空间为改线程分配java栈。因为一个线程必须对应一个Java虚拟机栈。这个我认为是JVM内存区域的异常。
这边我顺带在思考,HotSpot里面的Java虚拟栈是怎么样的一个数据结构,是顺序栈呢还是链式栈呢?
个人认为是顺序栈,首先out*异常+JVM的特性。使用链式栈空间要求更大,虽然栈帧不受限制,但是不受控的往往风险更大。但是具体的证据目前还在寻找中。
目前我认为Java虚拟机栈是一个数组实现的顺序栈。