## 栈 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