一、栈是什么？
栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素的操作，一般叫做push，入栈
从栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做弹出栈顶元素）
遵循先进后出，后进先出的原则
注意：这里所说的栈和栈空间是两个不同的概念，栈是一种数据结构，用来组织数据和存放数据的，而栈空间是内存的一种，是一种内存空间。
二、栈的接口设计
栈可以直接在链表的基础上去实现，运用组合的方式，让ArrayList成为栈的一部分，然后在此基础上实现栈的功能。
◼ int size(); // 元素的数量 ◼ boolean isEmpty(); // 是否为空 ◼ void push(E element ); // 入栈 ◼ E pop(); // 出栈 ◼ E top(); // 获取栈顶元素 ◼ void clear(); // 清空
public class Stack<E> { private List<E> list = new ArrayList<>(); public void clear() { list.clear(); } public int size() { return list.size(); } public boolean isEmpty() { return list.isEmpty(); } public void push(E element) { list.add(element); } public E pop() { return list.remove(list.size() - 1); } public E top() { return list.get(list.size() - 1); } }
三、栈的常用方法
| 方法 | 功能 |
Stack() |
构造一个空的栈 |
E push(E e) |
将e入栈，并返回e |
E pop() |
将栈顶元素出栈并返回 |
E peek() |
获取栈顶元素 |
int size() |
获取栈中有效元素个数 |
boolean empty() |
检测栈是否为空 |
四、栈的底层是什么？
通过观察源码，我们可以发现，Stack继承了Vector。
Vector是用数组实现的，所以栈的底层是数组。
五、栈的自实现（数组、单链表、双向链表）
一：用数组自实现：
public class MyStack { int[] elem; int usesize; static final int DEFAULT_SIZE = 10; public MyStack(){ this.elem = new int[DEFAULT_SIZE]; } public int push(int val){ if (isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } elem[usesize] = val; usesize++; return val; } public boolean isFull(){ return usesize == elem.length; } public int pop(){ if (empty()){ throw new MyEmptyStackException("栈为空！"); } return elem[--usesize]; } public boolean empty(){ return usesize == 0; } public int peek(){ if (empty()){ throw new MyEmptyStackException("栈为空！"); } return elem[usesize-1]; } }
二：用单链表的也可以实现，其中入栈用头插，出栈也是在头部，时间复杂度为O(1)。当然双向链表也可以实现栈，而且头尾都可以作为出栈和入栈。
六、栈的应用（浏览器的前进后退、根据逆波兰表达式求值）
浏览器的前进和后退其实就是用到了栈。
当我们连续输入三个网站，比如，baidu.com,taobao.com,qq.com
这个时候这三个网站可以前进和后退，其实这里是用到了两个栈。
但是当我们后退到中间位置时，即没有在最后进来的网站的时候，这个时候我们再次输入bilibili.com的时候，在之前位置的后面的网站全都清空了，把新加进来的网站做为最新的最后的网站。
根据逆波兰表达式求值：
中缀表达式转后缀表达式（逆波兰式）：
用栈实现计算后缀表达式：1 2 3 * + 4 5 * 6 + 7 * +
方法：遇到数字入栈，遇到运算符出栈顶的两个元素，其中弹出的第一个是右操作数，第二个是左操作数。
七、栈、虚拟机栈、栈帧有什么区别呢？
栈是一种先进后出的数据结构。
虚拟机栈是JVM的一块内存空间。
栈帧是在函数的调用过程中，在java虚拟机栈上开辟的一块内存。
