## 栈 Stack
* 栈是一种特殊的**线性表**, 只能在一端（栈顶）进行操作
* 向栈中**添加元素**的操作，即 push，入栈，压栈
* 从栈中**移除元素**的操作(只能移除栈顶的元素)，即 pop，出栈，弹栈
* 栈遵循**后进先出**原则：Last In First Out，LIFO
## 实现栈
* 栈的内部实现可以使用**动态数组**或**双向链表**，因为栈的主要操作是在尾部添加或删除元素，所以入栈出栈复杂度都是 $ O(1) $（注意必须是双向链表，才能保证 $ O(1) $ 的复杂度）
* 虽然可以继承 ArrayList 或 LinkedList 来实现栈，但是 ArrayList 或 LinkedList 中栈不需要的方法也会继承过来，比如向栈中某位置插入或删除
* 可以使用**组合**的方式实现栈，即在栈的类**内部**声明一个私有的 ArrayList 或 LinkedList 对象供自己使用
* JDK 源码的原生 Stack 数据结构继承于 Vector（Vector 可以看做是线程安全的 ArrayList）
```java
import java.util.ArrayList;
import java.util.List;
public class Stack {
// 声明一个 List 用于存储数据
private List list;
public Stack() {
// 也可以用我们自己写的 ArrayList 或者 LinkedList（双向链表） 实现
list = new ArrayList<>();
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void clear() {
list.clear();
}
// 将一个元素压入栈中
public void push(E ele) {
list.add(ele);
}
// 返回并弹出栈顶元素
public E pop() {
return list.remove(list.size()-1);
}
// 查看栈顶元素，但不弹出
public E top() {
return list.get(list.size()-1);
}
}
```
## 参考
* [恋上数据结构与算法（第一季）](https://ke.qq.com/course/385223)
* [小码哥《恋上数据结构与算法》笔记（五）：栈](https://juejin.im/post/5dfb12fd518825122e0a85bd)
数据结构 | 栈 Stack
