栈Stack

堆栈是“后进先出”（LIFO）集合。它有时被称为叠加栈（pushdown stack），因为最后“压入”（push）栈的元素，第一个被“弹出”（pop）栈。经常用来类比栈的事物是带有弹簧支架的自助餐厅托盘。最后装入的托盘总是最先拿出来使用的。

Java 1.0 中附带了一个 Stack 类，结果设计得很糟糕（为了向后兼容，永远坚持 Java 中的旧设计错误）。
Java 6 添加了 ArrayDeque ，其中包含直接实现堆栈功能的方法.
即使它是作为一个堆栈在使用，我们仍然必须将其声明为 Deque 。有时一个名为 Stack 的类更能把事情讲清楚：

基本上，这个类是在声明“我们在定义一个可以持有 T 类型对象的 Stack 。” Stack 是使用 ArrayDeque 实现的，而 ArrayDeque 也被告知它将持有 T 类型对象。

• push() 接受类型为 T 的对象
• peek() 和 pop() 返回类型为 T 的对象
  • peek() 方法将返回栈顶元素，但并不将其从栈顶删除
  • pop() 删除并返回顶部元素

如果只需要栈的行为，使用继承是不合适的，因为这将产生一个具有 ArrayDeque 的其它所有方法的类（Java 1.0 设计者在创建 java.util.Stack 时，就犯了这个错误）。
使用组合，可以选择要公开的方法以及如何命名它们。

尽管已经有了 java.util.Stack ，但是 ArrayDeque 可以产生更好的 Stack ，因此更可取。
可以使用显式导入来控制对“首选” Stack 实现的选择：

import com.javaedge.Stack;
   

现在,任何对 Stack 的引用都将选择 onjava 版本，而在选择 java.util.Stack 时，必须使用全限定名称.

Set

Set 不保存重复的元素.Set 最常见的用途是测试归属性，可以很轻松地询问某个对象是否在一个 Set 中。因此，查找通常是 Set 最重要的操作，因此通常会选择 HashSet 实现，该实现针对快速查找进行了优化。

Set 与 Collection 拥有相同接口，因此无任何额外功能，不像前面两种不同类型的 List 。实际上， Set 就是一个 Collection  ，只是行为不同。

这是继承和多态思想的典型应用：表现不同的行为.

Set 根据对象的“值”确定归属性.

早期 Java 版本中的 HashSet 产生的输出没有可辨别的顺序。这是因为出于对速度的追求， HashSet 使用了散列。由 HashSet 维护的顺序与 TreeSet 或 LinkedHashSet 不同，因为它们的实现具有不同的元素存储方式。
TreeSet 将元素存储在红-黑树数据结构中，而 HashSet 使用散列函数。

LinkedHashSet也使用了散列，使用了链表来维护元素的插入顺序。看起来散列算法好像已经改变了，现在 Integer 按顺序排序。

要对结果进行排序，一种方法是使用 TreeSet 而不是 HashSet ：

最常见的操作之一是使用 contains() 测试成员归属性，但也有一些其它操作

能够产生每个元素都唯一的列表是相当有用的功能。
排序是按字典顺序（lexicographically）完成的，因此大写和小写字母位于不同的组中。如果想按字母顺序（alphabetically）对其进行排序，可以向  TreeSet 构造器传入 String.CASE_INSENSITIVE_ORDER 比较器.

Map

将对象映射到其他对象。

Map 与数组和其他的 Collection 一样，可以轻松地扩展到多个维度，只需要创建一个值为 Map 的 Map（这些 Map 的值可以是其他集合，甚至是其他 Map）。因此，能够很容易地将集合组合起来以快速生成强大的数据结构。
例如，假设你正在追踪有多个宠物的人，只需要一个 Map\<person, list\ 即可：

Map 可返回由其键组成的 Set ，由其值组成的 Collection ，或者其键值对的 Set 。
keySet() 方法生成所有键组成的 Set ，它在 for-in 语句中被用来遍历该 Map 。

队列Queu

先进先出集合。 即从集合的一端放入事物，再从另一端去获取它们，事物放入集合的顺序和被取出的顺序是相同的。
队列通常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中尤为重要，因为它们可以安全地将对象从一个任务传输到另一个任务。

LinkedList 实现 Queue 接口，并提供了一些方法以支持队列，因此 LinkedList 可用作 Queue 的一种实现。 通过将 LinkedList 向上转换为 Queue .

• offer() 是与 Queue 相关的方法之一，它在允许的情况下，在队列的尾部插入一个元素，或者返回 false 。

• peek() 和 element() 都返回队头元素而不删除它，但是如果队列为空，则

  • element() 抛出 NoSuchElementException
  • peek() 返回 null

• poll() 和 remove()都删除并返回队头元素，但如果队列为空

  • poll() 返回 null
  • remove() 抛出 NoSuchElementException

  Queue 接口窄化了对 LinkedList 方法的访问权限，因此只有适当的方法才能使用，因此能够访问到的 LinkedList 的方法会变少（实际上可以将 Queue 强制转换回 LinkedList ，但不鼓励这样做）。

与 Queue 相关的方法提供了完整而独立的功能。 也就是说，对于 Queue 所继承的 Collection ，在不需要使用它的任何方法的情况下，就可以拥有一个可用的 Queue 。

优先级队列PriorityQueue

先进先出描述了最典型的队列规则（queuing discipline）。队列规则是指在给定队列中的一组元素的情况下，确定下一个弹出队列的元素的规则。

先进先出声明的是下一个弹出的元素应该是等待时间最长的元素。
优先级队列声明下一个弹出的元素是最需要的元素（具有最高的优先级）。例如，在机场，当飞机临近起飞时，这架飞机的乘客可以在办理登机手续时排到队头。如果构建了一个消息传递系统，某些消息比其他消息更重要，应该尽快处理，而不管它们何时到达。在Java5 中添加了 PriorityQueue ，以便自动实现这种行为。

当在 PriorityQueue 上调用 offer() 方法来插入一个对象时，该对象会在队列中被排序。[^5]默认的排序使用队列中对象的自然顺序（natural order），但是可以通过提供自己的 Comparator 来修改这个顺序。 PriorityQueue 确保在调用 peek() ， poll() 或 remove() 方法时，获得的元素将是队列中优先级最高的元素。

PriorityQueue 允许重复，最小的值具有最高的优先级（如果是 String ，空格也可以算作值，并且比字母的优先级高）。
Integer ， String 和 Character 可以与 PriorityQueue 一起使用，因为这些类已经内置了自然排序。如果想在 PriorityQueue 中使用自己的类，则必须包含额外的方法以产生自然排序，或者必须提供自己的 Comparator 。

集合 VS 迭代器

Collection 是所有序列集合的根接口。它可能会被认为是一种“附属接口”，即因为要表示其他若干个接口的共性而出现的接口。
java.util.AbstractCollection 类提供了 Collection 的默认实现，使得你可以创建 AbstractCollection 的子类型，而其中没有不必要的代码重复。

使用接口描述的一个理由是它可以使我们创建更通用的代码。通过针对接口而非具体实现来编写代码，我们的代码可以应用于更多类型的对象。因此，如果所编写的方法接受一个 Collection ，那么该方法可以应用于任何实现了 Collection 的类——这也就使得一个新类可以选择去实现 Collection 接口，以便该方法可以使用它。

标准 C++ 类库中的的集合并没有共同的基类——集合之间的所有共性都是通过迭代器实现的。在 Java 中，遵循 C++ 的方式看起来似乎很明智，即用迭代器而不是 Collection 来表示集合之间的共性。

但是， Java中这两种方法绑定在了一起，因此实现 Collection 就意味着需要提供 iterator() 方法.
都可以使用 Map 或 Collection 的子类型来工作。 而且Collection 接口和 Iterator 都将方法与底层集合的特定实现解耦。
事实上， Collection 要更方便一点，因为它是 Iterable 类型，因此在 display(Collection) 的实现中可以使用 for-in 构造，这使得代码更加清晰。

当需要实现一个不是 Collection 的外部类时，由于让它去实现 Collection 接口可能非常困难或麻烦，因此使用 Iterator 就会变得非常吸引人。
例如，如果我们通过继承一个持有 Pet 对象的类来创建一个 Collection 的实现，那么我们必须实现 Collection 所有的方法，即使我们不在 display() 方法中使用它们，也必须这样做。虽然这可以通过继承 AbstractCollection 而很容易地实现，但是无论如何还是要被强制去实现 iterator() 和 size() 方法，这些方法 AbstractCollection 没有实现，但是 AbstractCollection 中的其它方法会用到：
你可能会认为，因为 iterator() 返回 Iterator\ ，匿名内部类定义可以使用菱形语法，Java可以推断出类型。但这不起作用，类型推断仍然非常有限。

如果实现 Collection ，就必须实现 iterator() ，并且只拿实现 iterator() 与继承 AbstractCollection 相比，花费的代价只略微减少。
但是，如果类已经继承其他类，就不能再继承 AbstractCollection 。这种情况，要实现 Collection ，就必须实现该接口中的所有方法。此时，继承并提供创建迭代器的能力要容易得多.

生成 Iterator 是将序列与消费该序列的方法连接在一起耦合度最小的方式，并且与实现Collection 相比，它在序列类上所施加的约束也少。

for-in和迭代器

for-in 语法主要用于数组，但它也适用于任何 Collection 对象。
原因是 Java 5 引入了一个名为 Iterable 的接口，该接口包含一个能够生成 Iterator 的 iterator() 方法。for-in 使用此 Iterable 接口来遍历序列。因此，如果创建了任何实现了 Iterable 的类，都可以将它用于 for-in 语句中：

iterator() 返回的是实现了 Iterator\ 的匿名内部类的实例，该匿名内部类可以遍历数组中的每个单词。在主方法中，可以看到 IterableClass 确实可以用于 for-in 语句。

在 Java 5 中，许多类都是 Iterable ，主要包括所有的 Collection 类（但不包括各种 Maps ）。 

for-in 语句适用于数组或其它任何 Iterable ，但这并不意味着数组肯定也是个 Iterable ，也不会发生任何自动装箱.尝试将数组作为一个 Iterable 参数传递会导致失败。这说明不存在任何从数组到 Iterable 的自动转换; 必须手工执行这种转换。

适配器方法惯用法

如果现在有一个 Iterable 类，你想要添加一种或多种在 for-in 语句中使用这个类的方法，应该怎么做呢？例如，你希望可以选择正向还是反向遍历一个单词列表。如果直接继承这个类，并覆盖 iterator() 方法，则只能替换现有的方法，而不能实现遍历顺序的选择。

一种解决方案是所谓适配器方法（Adapter Method）的惯用法。“适配器”部分来自于设计模式，因为必须要提供特定的接口来满足 for-in 语句。如果已经有一个接口并且需要另一个接口时，则编写适配器就可以解决这个问题。
在这里，若希望在默认的正向迭代器的基础上，添加产生反向迭代器的能力，因此不能使用覆盖，相反，而是添加了一个能够生成 Iterable 对象的方法，该对象可以用于 for-in 语句。

小结

Java 提供了许多保存对象的方法：

1. 数组将数字索引与对象相关联。它保存类型明确的对象，因此在查找对象时不必对结果做类型转换。它可以是多维的，可以保存基本类型的数据。虽然可以在运行时创建数组，但是一旦创建数组，就无法更改数组的大小
2. Collection 保存单一元素，而 Map 包含相关联的键值对。使用 Java 泛型，可以指定集合中保存的对象的类型，因此不能将错误类型的对象放入集合中，并且在从集合中获取元素时，不必进行类型转换。各种 Collection 和各种 Map 都可以在你向其中添加更多的元素时，自动调整其尺寸大小。集合不能保存基本类型，但自动装箱机制会负责执行基本类型和集合中保存的包装类型之间的双向转换
3. 像数组一样， List 也将数字索引与对象相关联，因此，数组和 List 都是有序集合
4. 如果要执行大量的随机访问，则使用 ArrayList ，如果要经常从表中间插入或删除元素，则应该使用 LinkedList
5. 队列和堆栈的行为是通过 LinkedList 提供的
6. Map 是一种将对象（而非数字）与对象相关联的设计。 HashMap 专为快速访问而设计，而 TreeMap 保持键始终处于排序状态，所以没有 HashMap 快。LinkedHashMap 按插入顺序保存其元素，但使用散列提供快速访问的能力
7. Set 不接受重复元素。 HashSet 提供最快的查询速度，而 TreeSet 保持元素处于排序状态。 LinkedHashSet 按插入顺序保存其元素，但使用散列提供快速访问的能力
8. 不要在新代码中使用遗留类 Vector ，Hashtable 和 Stack

简单集合分类

实际上只有四个基本的集合组件： Map ， List ， Set 和 Queue ，它们各有两到三个实现版本（Queue 的 java.util.concurrent 实现未包含在此图中）。最常使用的集合用黑色粗线线框表示。

虚线框表示接口，实线框表示普通的（具体的）类。带有空心箭头的虚线表示特定的类实现了一个接口。实心箭头表示某个类可以生成箭头指向的类的对象。例如，任何 Collection 都可以生成 Iterator ， List 可以生成 ListIterator （也能生成普通的 Iterator ，因为 List 继承自 Collection ）。

除 TreeSet 之外的所有 Set 都具有与 Collection 完全相同的接口。List 和 Collection 存在着明显的不同，尽管 List 所要求的方法都在 Collection 中。另一方面，在 Queue 接口中的方法是独立的，在创建具有 Queue 功能的实现时，不需要使用 Collection 方法。最后， Map 和 Collection 之间唯一的交集是 Map 可以使用 entrySet() 和 values() 方法来产生 Collection 。

请注意，标记接口 java.util.RandomAccess 附加到了 ArrayList 上，但不附加到 LinkedList 上。这为根据特定 List 动态改变其行为的算法提供了信息。

从面向对象的继承层次结构来看，这种组织结构确实有些奇怪。但是，当了解了 java.util 中更多的有关集合的内容后，就会发现出了继承结构有点奇怪外，还有更多的问题。集合类库一直以来都是设计难题——解决这些问题涉及到要去满足经常彼此之间互为牵制的各方面需求。所以要做好准备，在各处做出妥协。

尽管存在这些问题，但 Java 集合仍是在日常工作中使用的基本工具，它可以使程序更简洁、更强大、更有效。