【数据结构】栈（stack）
目录
栈的概念
栈的方法
栈的实现
数组实现
push方法 压栈
pop方法 出栈
peek方法 获取栈顶元素
size方法 获取有效元素个数
链表实现
结尾
完整代码
数组实现栈代码
双向链表实现栈代码
栈的概念
栈是一种特殊的线性表，只允许在 固定的一段 进行插入和删除数据，配合下面图能有更清楚的认识。
压栈：栈的插入顺序叫做进栈/压栈/入栈，入数据在栈底
出栈：栈的删除操作叫做出栈，出数据在栈顶
栈里面放数据的顺序是 12 23 34，取出数据的顺序是34 23 12
更形象一点的例子，是枪子弹的打出顺序，最后的放进去的子弹会先被打出，
栈从虚拟机的角度有个特点：先进的后出
栈的方法
栈的方法有一下六种
栈的实现
栈可以从数组方面实现，也可以从链表方面实现，下面会有对应的演示。
数组实现的栈叫做 顺序栈，链表实现的栈叫做 链式栈。
数组实现
先定义基本变量，因为是数组实现栈，所以定义数组elem以及useSize记录数组中有效元素个数。
public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}
}
push方法 压栈
public void push(int val){elem[useSize] = val;useSize++;}这部分代码看起来是符合我们要求的，是要把 val值 放入到 elem数组中，但这是一般情况，如果我们放 val值 时数组满了，是不是需要给数组扩容，这时候我们可以写一个判断数组是否为满的方法（isFull方法）。因为这个方法只有push方法才用得到，所以用private。
private boolean isFull(){return useSize == elem.length;}push方法完整为以下代码：
public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}pop方法 出栈
pop方法的功能是把栈顶的元素移出栈，同时打印一遍。在移除元素之前，要考虑到栈里有没有元素，没有元素就无法移除。所以需要写一个方法来判断（isEmpty方法）。
private boolean isEmpty(){return useSize == 0;}对于移除栈顶的元素，也就是最后加入的元素，我们可以采用useSize-1来实现，这样就能在打印数组的时候不去打印出栈顶的元素。
public int pop(){if(isEmpty()){System.out.println("栈为空");//这里也可以写个异常来提醒}int cur = elem[useSize-1];useSize--;return cur;}如果要写一个异常来提醒的话，需要再写一个异常类
对应的pop方法为
public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}peek方法 获取栈顶元素
获取栈顶元素在上面的出栈方法中也提到了，不过上面是要把栈顶元素删除，这里只需要返回即可。
public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}
size方法 获取有效元素个数
这里其实在定义初始变量的时候也有提到，便是其中 useSize 所代表的意思。
public int size(){return useSize;}链表实现
用链表实现栈，推荐使用双向链表来实现
因为 入栈 不管是头插法还是尾插法都可以是心啊，时间复杂度都是O(1)。
public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}
结尾
区分三种不同的概念
栈：是一种数据结构
虚拟机栈：是JVM中一类内存
栈帧：是运行一个函数/方法，给这个函数开辟的一个内存
完整代码
数组实现栈代码
CheckEmptyException类
public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}
MyStack类
import java.util.Arrays;public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}private boolean isEmpty(){return useSize == 0;}public int size(){return useSize;}
}
双向链表实现栈代码
public static void main(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack);}