常用数据结构和技巧
字符串
字符串的处理更多的是转换成字符数组对每一个字符进行处理。
链表
单链表：链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
双链表：单链表不同的是，双链表的每个结点中都含有两个引用字段。
解题技巧：
- 利用快慢指针。典型题目例如：链表的翻转，寻找倒数第 k 个元素，寻找链表中间位置的元素，判断链表是否有环等等。
- 构建一个虚假的链表头
训练技巧：在白板上画出节点之间的相互关系，画出修改的方法
栈
由于历史遗留问题，Java中没有Stack接口，通过Deque接口来模拟Stack。
当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。
队列
int size()：获取队列长度；boolean add(E)/boolean offer(E)：添加元素到队尾；E remove()/E poll()：获取队首元素并从队列中删除；E element()/E peek()：获取队首元素但并不从队列中删除。
添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。
| throw Exception | 返回false或null | |
|---|---|---|
| 添加元素到队尾 | add(E e) | boolean offer(E e) |
| 取队首元素并删除 | E remove() | E poll() |
| 取队首元素但不删除 | E element() | E peek() |
双端队列
特点：双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。
实现：与队列相似，我们可以利用一个双链表实现双端队列。
应用场景：双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。
我们来比较一下Queue和Deque出队和入队的方法：
| Queue | Deque | |
|---|---|---|
| 添加元素到队尾 | add(E e) / offer(E e) | addLast(E e) / offerLast(E e) |
| 取队首元素并删除 | E remove() / E poll() | E removeFirst() / E pollFirst() |
| 取队首元素但不删除 | E element() / E peek() | E getFirst() / E peekFirst() |
| 添加元素到队首 | 无 | addFirst(E e) / offerFirst(E e) |
| 取队尾元素并删除 | 无 | E removeLast() / E pollLast() |
| 取队尾元素但不删除 | 无 | E getLast() / E peekLast() |
Deque是一个接口，它的实现类有ArrayDeque和LinkedList。
树
在面试中常考的树的形状有：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。
重点复习一下树的遍历问题。
高级数据结构
- 优先队列
- 图
- 线段树
- 前缀树
- 树状数组
高级数据结构的内容过于陌生，留到后面学习整理。先巩固基础的数据结构。