1.前言：数据结构——队列
队列接口先说明有哪些功能，但不说是如何实现的，队列有两种实现方式：
- 循环数组
- 链表
循环数组更加高效，但循环数组是个有界集合，容量有限，如果对象的数量没有上限，最好用链表来实现。
一旦构建了集合就不需要知道到底使用了哪种实现。所以可以使用接口类型存放集合的引用
List<String> list = new ArrayList<>();
list.add("abc");
如果我们想修改成另一种实现，只需要把ArrayList改成LinkedList。
2.Collection 接口
collection接口有两个基本方法：
// 如果添加元素确实改变了集合就返回 true;如果没有改变就返回 false，比如添加的元素已经存在就不会改变原集合
boolean add(E element);
// 迭代器，见下一点
Iterator<E> iterator();
3.迭代器
Iterator接口有4个方法：
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();
default void forEachRemaining(Student<? super E> stu);
}
反复调用 next() 方法，能逐个访问集合的每个元素，但如果访问到了集合的末尾，会抛出一个 NoSuchElementException，所以我们在调用next()前最好使用hasNext()检查下。
List<String> list = new ArrayList<>();
list.add("abc");
list.add("123");
list.add("qwe");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next()); // abc 123 qwe
}
当然，如果要循环一个集合，更简单的方法是使用forEach:
for (String s : list) {
System.out.println(s);
}
也可以使用forEachRemaining：
iterator.forEachRemaining(element -> System.out.println(iterator.next()));
顺序问题：元素被访问的顺序取决于集合类型，如果对 ArrayList 进行迭代，迭代器将从索引0开始，每迭代一次，索引值加1。如果是 HashSet ，每个元素会按照某种特定的次序出现，虽然也能访问到所有元素，但顺序是随机的。
remove()删除的是上次调用 next 方法时返回的元素。所以调用 remove 之前必须要有 next 方法被调用。
4.集合中的接口
需要注意的是：数组支持的有序集合因为可以快速随机访问，所有最好提供一个整数索引来访问，链表最好使用迭代器来遍历。
5.Java 库中的具体集合
| 集合类型 | 描述 |
|---|---|
| ArrayList | 一种可以动态增长和缩减的索引序列 |
| LinkedList | 一种可以在任何位置进行高效地插入和删除操作的有序序列 |
| ArrayDeque | 一种用循环数组实现的双端队列 |
| HashSet | 一种没有重复元素的无序集合 |
| TreeSet | 一种有序集 |
| EnumSet | 一种包含枚举类型值的集 |
| LinkedHashSet | 一种可以记住元素插入次序的集 |
| PriorityQueue | 一种允许高效删除最小元素的集合 |
| HashMap | 一种存储键 / 值关联的数据结构 |
| TreeMap | 一种键值有序排列的映射表 |
| EnumMap | 一种键值属于枚举类型的映射表 |
| LinkedHashMap | 一种可以记住键 / 值添加次序的映射表 |
| WeakHashMap | 一种其值无用武之地后可以被垃圾回收器回收的映射表 |
| IdentityHashMap | 一种用 == 而不是 equals 比较键值的映射表 |
6.链表
数组列表的问题：从中间删除一个元素之后，该元素后面的元素都需要向前移动，在中间插入也是。
链表就没有这个问题。
链表让我想到了比特币的区块结构，看图吧
每个 Link 可以看成一个节点，每个节点存放着前一个节点的引用和后一个节点的引用，所以链表实际上都是双向链接的。回到数组列表的问题，当我们需要插入一个元素的时候，只需要修改该节点以及其前后节点的引用就可以了。
但链表不支持快速的随机访问，如果要查看第100个元素，就必须从头开始，越过99个元素。所以如果程序需要采用整数索引访问元素时，通常不选用链表。
7.数组列表
List 接口用于描述一个有序集合，并且集合中每个元素的位置十分重要。有两种访问元素的协议：
- 用迭代器
- 用 get 和 set 方法随机访问每个元素
8.散列集
如果我们想要访问某个元素，但又忘了它的位置，这时候就需要散列集。该集运用的数据结构为散列表（hash table）。散列表会为每个对象计算一个整数，成为散列码（hash code）。散列码是由对象的实例域产生的。比如下表。
| 字符串 | 散列码 |
|---|---|
| "Lee" | 76268 |
| "lee" | 107020 |
| "eel" | 100300 |
如果是我们自己定义的类，就要实现这个类的hashCode()方法，同时还有equals()方法。
set 类型：set 是没有重复元素的元素集合。set 的 add 方法首先会集中查找要添加的对象，如果不存在，就将这个元素添加进去。
9.数集
TreeSet可以看成一个有序的散列集。当添加的时候会比较慢，但查询会比散列集快很多。
使用数集必须能比较元素，所有必须实现 comparable 接口。
10.队列与双端队列
队列可以让人们有效的在尾部添加一个元素，在头部删除一个元素。有两个端头的队列，即为双端队列，可以让人们有效的在头部和尾部同时添加或删除元素。不支持在队列中添加元素。Deque 接口由 ArrayDeque 和 LinkedList 实现。
11.优先级队列
优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行索引。也就是说，无论何时调用 remove 方法，总是获得当前优先级队列中最小的元素。
12.映射的两个实现
-
HashMap：散列映射对键进行散列。 -
TreeMap：树映射用键的整体顺序对元素进行排序，并将其组织成搜索树。
如果不需要按照一定顺序访问键，就选择散列，因为散列更快一些。
一些基本的操作：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
String myName = maps.get("second");
System.out.println(myName); // zyc
键必须是唯一的，如果 put 的键是重复的，则会覆盖前一个。而且 put 会返回被覆盖的那个值。
13.迭代
- 利用 forEach 和 lambda 表达式：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.forEach((k,v) ->
System.out.println("key:" + k +",val:" + v));
- 利用迭代器：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
Iterator<Map.Entry<String,String>> entryIterator = maps.entrySet().iterator();
entryIterator.forEachRemaining(System.out::println);
// entryIterator.forEachRemaining(element -> System.out.println(element));
14.Merge
当有这样一个需求：需要更新/新增的映射项在映射存在或者不存在的时候会进行不同的操作，这时候就需要用上merge 了。具体看代码吧
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.merge("first","i am new",(oldVal, newVal) -> {
System.out.println("1执行了:" + oldVal + "," + newVal);
return oldVal;
});
maps.merge("first1","i am new",(oldVal, newVal) -> {
System.out.println("1执行了:" + oldVal + "," + newVal);
return oldVal;
});
maps.forEach((k,v) ->
System.out.println("key:" + k +",val:" + v));
/*
1执行了:ethan,i am new
key:third,val:zyy
key:first1,val:i am new
key:first,val:ethan
key:second,val:zyc
*/
因为first已经存在了，所以会执行后面的函数，而first1不存在，所以根本就没有执行后面的值，而是仅仅把i am new设为first1对应的值。
15.映射视图
虽然很多数据结构认为映射属于集合，但在 java 中，映射并不在集合框架中。不过映射视图是实现了 Collection 的对象。视图包括键集合、值集合以及键值对集合。并且对三者进行remove操作会影响原视图。键是不能重复的，所以直接删除，但值时可以重复的，这里只删除了其中一个，不建议以删除值来删除键值对。
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.put("forth","zyc");
Set<String> keys = maps.keySet();
Collection<String> vals = maps.values();
Set<Map.Entry<String,String>> keyVals = maps.entrySet();
System.out.println(keys);
System.out.println(vals);
System.out.println(keyVals);
keys.remove("first");
vals.remove("zyc");
System.out.println(keyVals);
/*
[third, forth, first, second]
[zyy, zyc, ethan, zyc]
[third=zyy, forth=zyc, first=ethan, second=zyc]
[third=zyy, second=zyc]
*/
