Java中的栈
刷力扣时发现很少有人用Stack建栈,大部分都用双端队列接口Deque,出于对知识的渴望（就是菜）查阅了相关资料记录一下。
Stack类
Java 中的 Stack 类从 Vector 类继承，底层是用数组实现的线程安全的栈。不过Java中用来表达栈的功能（push/pop/peek），更适用的是使用双端队列接口Deque，并用实现类ArrayDeque/LinkedList来进行初始化。
1 | Deque<Object> stack = new ArrayDeque<>(); |
使用Deque而不用Stack的原因
设计方面：Java中的类只能继承一个类，而可以实现多个接口，因此用双端队列 Deque 来建栈比使用 Stack 要灵活的多。
不一致性：Stack 类扩展了 Vector 类，该类允许你按索引访问元素，与Stack的操作不一致。 而Deque接口不允许使用索引访问元素，Deque 接口允许的操作与 FIFO 或 LIFO 数据结构允许的一致。
从性能来说：Stack 扩展的 Vector 类是线程安全的，其实多数情况下并不需要做到线程安全，因此没有必要使用Stack。毕竟保证线程安全需要上锁，有额外的系统开销。另外，使用不必要的功能扩展其他类会使对象膨胀，从而可能会花费大量额外的内存和性能开销。
迭代顺序：Stack 和 Deque 的迭代顺序完全相反。Deque 的迭代顺序更符合栈。
1
2
3
4
5
6
7
8
9
10
11
12Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3
Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1
ArrayDeque 和 LinkedList 哪个更好？
ArrayDeque：底层使用数组存储，容量不够时需要扩容和数组拷贝，通常容量不会填满，会有空间浪费；
LinkedList：底层使用链表存储，每次push都需要new Node节点，并且node节点里面有prev和next成员，也会有额外的空间占用。
那么在用作栈时ArrayDeque 和 LinkedList 哪个更好？
注意到 ArrayDeque 源码注释中有一句话：
This class is likely to be faster than {@link Stack} when used as a stack,and faster than {@link LinkedList} when used as a queue.
ArrayDeque用作栈时比Stack快没有疑问，用作队列的时候似乎也会比LinkedList快！
经过测试后发现，ArrayDeque 确实比 LinkedList 要快一点，但是区别不大
总结
ArrayDeque会略胜一筹，不过差别通常可以忽略，笔者更倾向于使用 ArrayDeque
