栈
栈算是一种特殊的线性表，有后进先出的特性，只需要在一端进行入栈（插入数据）或者出栈（删除数据）的操作。要实现的话从数组和链表两方面来考虑。
数组实现
一般选择数组下标最小的作为栈底，设置一个top表示当前栈顶的位置，如果插入一个元素，先判断栈还有没有容量，有的话就把top++，然后元素放到当前top上。如果删除元素就让一个值等于当前元素，然后top--。
初始化的时候，要把top设置为-1，表示栈空，如果top等于数组的容量capacity - 1，就代表栈满了。
链表实现
每次插入一个节点，就把该节点的next指针指向当前栈顶的元素。而删除节点的时候，就让top指针指向栈顶元素的next指针，然后栈顶元素的next就可以设置为null。可以说是没有头结点的单链表。
队列
队列是先进先出的特性，从一端增加数据（入队），从另一端删除数据（出队）。删除这端叫做队头，增加这个是队尾。
顺序队列
一个front队头指针，一个rear队尾指针，初始化的时候两个都指向位置0，如果插入数据的话，就放到队尾指针的元素，然后rear++。如果删除就取出队头的元素，然后front++。这样子就会造成一个问题，因为出队后front++，而capacity不会变，那么这个队列的容量就会一直变小，所以循环队列出现了。
循环队列
如果是一个圈的话，就不会出现有空间浪费的情况。初始化两个指针都是0，如果队列满了，这两个指针的位置就会相等，就无法判断队列是空还是满，所以在最后设置一个元素空间，这个空间不会用来放任何元素，如果（rear + 1） & QueueSize == front的话就表示队列满了。出队和入队的时候，front或者rear + 1后都要对QueueSize取模。
链式存储
入队的话，rear的next指向入队元素，然后rear指针指向入队元素。出队的话，先取出元素的值，然后队头指针指向该元素的next，如果这个时候队尾也指向该元素，那么队尾指针等于队头指针，表示队列为空，然后把该元素的next变为null。
二叉树
- 二叉树第i层的节点数最多为2的i-1次方
- 非空二叉树叶子节点数等于度为2的节点数+1，即n0 = n2 + 1；
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
完全二叉树的性质有 n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。即log2n向下取整然后+1。
二叉排序树一般用于查找，性质有左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。
平衡二叉树的定义：根节点的左右子树高度之差不能超过1，在构建的时候如果某颗子树不是平衡的，就对于一整个子树进行调整，变成平衡二叉树，然后在放回原来子树的位置。
已知平衡二叉树的深度为k，那么平衡二叉树最少节点数为N(k)=F（k + 2） - 1，即斐波那契数列对应k+2的值-1，最大节点数就是满二叉树了，那么就是2的n次方 - 1
二叉树存储结构
可以用数组顺序存储，一个根节点有值val，左孩子，右孩子三个属性。遇到数组存放null值就把所有设置为空。如果是链表来构建的话，每个节点都有值和两个指针，指针分别指向左孩子右孩子的值。
计算hash值
- 直接定址法：定一个公式f（key）= a * key + b；直接通过计算来得知该存放的位置
- 除留余数法：对key取模，得出存放的位置f（key） = key mod p，一般p选接近于表长的最小质数
处理hash冲突方法
- 开放地址法：一旦遇到冲突我就寻找下一个空的散列地址，然后存进去。
- 链地址法：如果遇到冲突，把这个位置变成一个单链表，就是java中的hashmap在jdk1.7之前的解决方法。
- 再散列函数法：准备多个散列函数，如果这个发生冲突，就换下一个函数进行计算。
