大O描述的是算法的运行时间和输入数据之间的关系
O(1), O(n)，O(lgn),O(nlogn),O(n^2)
n是nums中的元素个数
均摊复杂度和防止复杂度的震荡
栈也是一种线性结构
相比数组，栈对应的操作是数组的子集
只能从一端添加元素，也只能从一端取出元素
这一端称为栈顶
栈是一种后进先出的数据结构
Last in First Out（LIFO）
栈的实现：Stack<E>
void push(E)
E pop()
E peek()
int getSize()
boolean isEmpty()
栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素
import java.util.Stack;
class Solution{
public boolean isValid(String s){
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length(); i++){
char c = s.charAt(i);
if(c == '(' || c =='[' || c == '{'){
stack.push(c);
}else{
if(stack.isEmpty()){
return false;
}else{
char topChar = stack.pop();
if(c == '(' && topChar != ')'){
return false
}
if(c == '[' && topChar != ']'){
return false
}
if(c == '{' && topChar != '}'){
return false
}
}
}
}
}
return stack.isEmpty();
}
队列 QUEUE
队列也是一种线性结构
相比数组，队列对应的操作是数组的子集
只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
队列是一种先进先出的数据结构
First in First out
FIFO
队列的实现
Queue<E>
void enqueue()
E dequeue()
E getFront()
int getSize()
boolean isEmpty()
循环队列
什么是链表
线性数据结构
动态数组
栈
队列
--------底层依托静态数组；靠resize解决固定容量问题
链表linkedList
public E e;
public Node nextElement;
数据存储在节点（Node）中
优点：真正的动态，不需要处理固定容量的问题
缺点：丧失了随机访问的能力
数组和链表的对比：
数组最好用于索引有语意的情况。array[2]
最大的优点：支持快速查询
链表不适合用于索引有语意的情况。
最大的优点：动态
程序调用的系统栈
递归调用时有代价的：函数调用+系统栈空间
二叉堆是一棵完全二叉树
二叉堆得性质:
堆中某个节点的值总是不大于其父节点
什么是Trie（字典树）--多叉树
每个节点有若干指向下个节点的指针
class Node{
boolean isWord;
Map<char,Node> next;
}
平衡二叉树（AVL树）
对于任意一个节点，左子树和右子树的高度差不能为超过1
平衡二叉树的高度和节点数量之间的关系也是O(logn)的二叉树
平衡因子:左子树的高度减去右子树的高度
左右节点的高度差
AVL树的左旋转和右旋转
加入节点后，沿着节点向上维护平衡性
什么是红黑树
1.每个节点或者是红色的，或者是黑色的
2.根节点是黑色的
3.每一个叶子节点（最后的空节点）是黑色的
4.如果一个节点是红色的，那么他的孩子节点都是黑色的
5.从任意一个节点到叶子节点，经过的黑色节点是一样的
2-3树
满足二分搜索树的基本性质
节点可以存放一个元素或者两个元素
每个节点有2个或3个孩子 ------ 2-3树
2-3树是一颗绝对平衡的树
红黑树和2-3树的等价性
所有的红色节点都是向左倾斜的
三个元素的节点会产生一个红色节点
（二三树中的三节点的左侧（较小的元素）为红节点）
其子节点为黑节点
黑节点的右侧子节点为黑节点
红黑树是保持“黑平衡”的二叉树
标签: 算法与数据结构
