介绍数据结构中的栈，队列，二叉树（完全二叉树，满二叉树，完美二叉树），二叉查找树，堆，哈希表以及算法中的一些排序算法和简单搜索算法
1 栈（stack）
特点：先进后出
push(S,x):将x推入S中
pop(S):取出一个栈顶元素
top():返回栈顶元素
isEmpty(S):栈为空返回true
| 操作 | 时间复杂度 |
|---|---|
| push | O(1) |
| pop | O(1) |
| top/peek | O(1) |
| search | O(n) |
应用：括号匹配问题，前中后序表达式prefix,Infix,Postfix
2 队列（Queue）
特点：先进先出
Enqueue(Q,x):元素x进入Q的队尾
Dequeue(Q):取出队头元素
注意：循环队列的情况，enqueue()和dequeue()的时间复杂度都是O(1)
3 二叉树 （Binary Tree）
定义：
高度(height)：从最底层叶子节点为0开始计算
深度(depth)：从根节点为0开始计算
节点(node)
完全二叉树（Complete BT）：深度为(d-1)的节点全部为满，深度为d的节点从左往右没有空
满二叉树（Full BT）：孩子节点为0或2个
完美二叉树（Perfect BT）：节点全部为满
对于完美二叉树，我们有高度（深度）和节点的关系表达：n=2^(h+1)-1
树的遍历(Tree traversal)
深度优先遍历(depth-first traversal)
前序遍历(Preorder)：父节点，左孩子，右孩子
中序遍历(Inorder)：左孩子，父节点，右孩子
后序遍历(Postorder)：左孩子，右孩子，父节点
宽度优先遍历(Breadth-first traversal)
二叉查找树(Binary Search Tree)
| Average | Worst | |
|---|---|---|
| Insert | O(logn) | O(n) |
| Delete | O(logn) | O(n) |
| Search | O(logn) | O(n) |
最坏情况就是变成了一个有序的单链表
Q：在BST中寻找某一个节点n的successor，也就是唯一比这个节点n大的节点
应用：删除BST中的某一个节点，得到新的BST
4 堆（Heap）
大顶堆(Max heap)：父节点比孩子节点大
小顶堆(Min heap)：父节点比孩子节点小
以Max heap为例，不同操作的时间复杂度如下
| 操作 | 时间复杂度 |
|---|---|
| Find max element | O(1) |
| Remove max element | O(logn) |
| Insert an element | O(logn) |
堆的高度（深度）与节点的关系表达：n>=2^h
5 哈希表（Hash Table）
目的：避免冲突(Collision)
几种方式：
Chaining：类似于链表，同一余数可以使用链表链接
Open Addressing
Linear probing：同一余数index+1
h(k,i)=(h0(k)+i) mod m,h0(k)=k mod m
Quadratic probing：同一余数继续计算
h(k,i)=(h0(k)+ai+bi^2) mod m,h0(k)=k mod m
了解影响因子(Load Factor)
6 排序算法（Sorting Algorithms）
7 搜索算法（Searching Algorithms）
| 查找方式 | 时间复杂度 |
|---|---|
| 线性查找(Linear search) | O(n) |
| 二分查找(Binary search) | O(logn) |
