数据结构快速回顾

线性表（有序表）

栈

队列（单向、双向）

字典（KV，无序）

树

图

一般分为：客户接口、实现

javadoc 生成

职责（方法用途）

前置（参数）、后置（返回值）条件

断言（测试用、生产环境下抛出异常）

根据角色 【用户】

根据场景

生成 用例图 辅助

CRC 【类责任协作卡】

UML 【统一建模语言】

void push(newEntry)

T pop()

T peek()

boolean isEmpty()

void clear

平衡表达式：括号对称等

中缀表达式 => 后缀表达式（圆括号处理：开圆括号为最低优先级运算符）

计算后缀表达式（不含有圆括号）

计算中缀表达式（两个栈）

程序栈（Java栈）

链式栈

数组栈

向量栈

【结构：KV（键值对）】

void add(key, value)

V remove(key)

V getValue(key)

boolean contains(key)

Iterator getKeyIterator()

Iterator getValueIterator()

int getSize()

void clear()

快速确定下标（快速获得 key 所在位置）

散列码（hashCode）

注意：如果类重写了 equals()，则也应该重写 hashCode()

结果：将 散列码 压缩为散列表的 下标

冲突：开放地址法（双散列）、拉链法（每个 key 对应多个 value 进行存储）

前序遍历

中序遍历

后序遍历

广度优先遍历

深度优先遍历

完全二叉树（有右必有左）

平衡二叉树（每个节点有高度相同的两个子树）

表达式树（a / b + c）

决策树（Yes || No）

二叉查找树（类似二分查找）

堆（最大 / 最小）

语法树

AVL 树（不平衡时自动重排）

红黑树（根黑，红父为黑，红孩都为黑，每条树枝都有相同个数的黑色节点）

B 树（m 阶多路查找树：根无或 2~m 个孩子，内部节点有 m/2~m 个孩子，叶子节点都在同一层）

有 环 否？

有 权 否？

有 方向 否？

连通（邻接） 否？

有向无环图

寻找路径

带权图中的最短路径（开发算法、跟踪算法）