Java编程思想——持有对象

11 持有对象

如果一个程序只包含固定数量的且生命周期都是已知的对象，那么这是一个非常简单的程序。
通常程序都是根据运行时才知道的某些条件去创建新对象，在此之前，不会知道所需对象的数量，甚至不知道确切的类型，这时候就不能依靠创建命名的引用来持有每一个对象，因为你不知道有多少个引用。java有多种方式保存对象，例如数组。但是数组具有固定的尺寸，在更一般的情况下，写程序的时候并不知道将要需要多少个对象，后者更复杂的方式存储对象。

java实用类库中还提供了一套相当完整的容器来解决这一问题，其中基本的类型是List、Set、Queue和Map。这些对象类型称之为集合类。java类库中使用了Collection这个名字来指代该类库的一个特殊子集，一般使用容器来程序来它们。这里介绍java容器类库的基本知识，以及典型用法的基本介绍。

11.1 泛型和类型安全的容器

使用java SE5之前的容器的一个主要问题是编译器允许你向容器中插入不正确的类型。例如考虑一个apple对象的容器，可以使用容器ArrayList。例如将apple对象和orange对象都放置在容器中，然后将它们取出。正常情况下，java编译器会报告警告信息，如果没有使用泛型的话。Apple类型和Orange类型是有区别的，除了都是Object之外没有任何共性，因为ArrayList保存的是Object，因此不仅可以通过ArrayList的add()方法将Apple对象放进这个容器，也可以添加Orange对象。但是当你使用ArrayList的get()方法取出来得到的是Object引用，不是Apple对象，必须要转型为Apple。当你试图将Orange转型为Apple时，会产生异常。如果想要定义保存Apple对象的ArrayList，可以声明ArrayList<Apple>,其中尖括号括起来的是类型参数，他指定了这个容器实例可以保存的类型。通过使用泛型，可以在编译期间防止将错误类型的对象放置在容器中。

11.2 基本概念

java容器类库的用途是”保存对象“，其中可以划分为两个不同的概念：

1. Collection 一个独立元素的序列，这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素，而Set不能有重复的元素。Queue按照队列规则来确定对象产生的顺序。
2. Map 一组成对的”键值对“对象，允许你使用键来查找值。ArrayList允许你使用数字来查找值，某种意义上讲，他将数字与对象关联在一起。映射表允许使用另一个对象来查找 某个对象，也被称为”关联数组“，因为它将某些对象与另外一些对象关联在了一起，或者被称之为字典

Collection接口概括了序列的概念——一种存放一组对象的方式。例如：用Integer对象填充了一个Collection,然后打印所产生的容器中的所有元素：

//: holding/SimpleCollection.java
import java.util.*;

public class SimpleCollection {
  public static void main(String[] args) {
    Collection<Integer> c = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++)
      c.add(i); // Autoboxing
    for(Integer i : c)
      System.out.print(i + ", ");
  }
} /* Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
*///:~

这个示例只使用了Collection方法，任何继承自Collection类都可以正常工作，而ArrayList是最基本的序列类型。

11.3 添加一组元素

在java.util包中的Arrays和Collections类中都有很多实用的方法，可以在一个Collection中添加一组元素。例如ArrayList.asList()方法和Collections.addAll()方法。接受一个数组或者一个用逗号分割的元素列表。

//: holding/AddingGroups.java
// Adding groups of elements to Collection objects.
import java.util.*;

public class AddingGroups {
  public static void main(String[] args) {
    Collection<Integer> collection =
      new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
    Integer[] moreInts = { 6, 7, 8, 9, 10 };
    collection.addAll(Arrays.asList(moreInts));
    // Runs significantly faster, but you can't
    // construct a Collection this way:
    Collections.addAll(collection, 11, 12, 13, 14, 15);
    Collections.addAll(collection, moreInts);
    // Produces a list "backed by" an array:
    List<Integer> list = Arrays.asList(16, 17, 18, 19, 20);
    list.set(1, 99); // OK -- modify an element
    // list.add(21); // Runtime error because the
                     // underlying array cannot be resized.
  }
} ///:~

Collection.addAll()方法运行起来很快，而且构造一个不含元素的Collection，然后调用Collections.addAll()这种方式很方便，因此是首选方式。

Collection.addAll()成员方法只能接受另一个Collection对象作为参数，因此它不如Arrays.asList()或Collections.addAll()灵活。

可以直接使用Arrays.asList()输出，将其当做List，但是这种情况下，其底层表示的是数组，因此不能调整尺寸，如果试图用add()或delete()方法在这种列表中添加或删除元素，就有可能会引发去改变数组尺寸的尝试，引发错误。

11.4 容器的打印

下面示例是各种基本类型容器的打印介绍：

//: holding/PrintingContainers.java
// Containers print themselves automatically.
import java.util.*;
import static net.mindview.util.Print.*;

public class PrintingContainers {
  static Collection fill(Collection<String> collection) {
    collection.add("rat");
    collection.add("cat");
    collection.add("dog");
    collection.add("dog");
    return collection;
  }
  static Map fill(Map<String,String> map) {
    map.put("rat", "Fuzzy");
    map.put("cat", "Rags");
    map.put("dog", "Bosco");
    map.put("dog", "Spot");
    return map;
  } 
  public static void main(String[] args) {
    print(fill(new ArrayList<String>()));
    print(fill(new LinkedList<String>()));
    print(fill(new HashSet<String>()));
    print(fill(new TreeSet<String>()));
    print(fill(new LinkedHashSet<String>()));
    print(fill(new HashMap<String,String>()));
    print(fill(new TreeMap<String,String>()));
    print(fill(new LinkedHashMap<String,String>()));
  }
} /* Output:
[rat, cat, dog, dog]
[rat, cat, dog, dog]
[dog, cat, rat]
[cat, dog, rat]
[rat, cat, dog]
{dog=Spot, cat=Rags, rat=Fuzzy}
{cat=Rags, dog=Spot, rat=Fuzzy}
{rat=Fuzzy, cat=Rags, dog=Spot}
*///:~

Collection在每个槽中只能保存一个元素。此类容器包括：List，它以特定的顺序保存一组元素；Set，元素不能重复；Queue，只允许容器在一端插入对象，并从另一端移除对象。
Map在每个槽内保存了两个对象，即键和与之相关联的值。

ArrayList和LinkedList都是List类型，他们都按照被插入的顺序保存元素。二者不同之处在于执行某行类型的操作性能，而且LinkedList包含的操作多于ArrayList。

HashSet，TreeSet和LinkedHashSet都是Set类型，每个相同的项只有保存一次。不同的Set实现存储元素的方式也不同，HashSet使用了相当复杂的方式来存储元素，如果存储顺序很重要，可以使用TreeSet，按照比较结果的升序保存对象；或者使用LinkedHashSet，它按照被添加的顺序保存对象。

Map（也称关联数组）使得你可以用键来查找对象，就像一个简单的数据库。键关联的对象称为值。键和值在Map中保存顺序并不是它们的插入顺序，因为HashMap实现使用的是一种非常快的算法来控制顺序。与HashSet一样，HashMap提供了最快的查询技术，也没有按照任何明显得顺序保存其元素。而LinkedHashMap按照插入顺序保存键，同时还保留了HashMap的查询速度。

11.5 List

List接口在Collection基础上添加了大量的方法，使得可以在List的中间插入和移除元素。由两种类型的List：

• 基本的ArrayList，它长于随机访问元素，但是在List的中间插入和移除元素时较慢。
• LinkedList，通过代价较低的在List中间插入和删除操作，提供了优化的顺序访问，LinkedList在随机访问方面相对比较慢，但是它的特性集较ArrayList更大。

//: holding/ListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;

public class ListFeatures {
  public static void main(String[] args) {
    Random rand = new Random(47);
    List<Pet> pets = Pets.arrayList(7);
    print("1: " + pets);
    Hamster h = new Hamster();
    pets.add(h); // Automatically resizes
    print("2: " + pets);
    print("3: " + pets.contains(h));
    pets.remove(h); // Remove by object
    Pet p = pets.get(2);
    print("4: " +  p + " " + pets.indexOf(p));
    Pet cymric = new Cymric();
    print("5: " + pets.indexOf(cymric));
    print("6: " + pets.remove(cymric));
    // Must be the exact object:
    print("7: " + pets.remove(p));
    print("8: " + pets);
    pets.add(3, new Mouse()); // Insert at an index
    print("9: " + pets);
    List<Pet> sub = pets.subList(1, 4);
    print("subList: " + sub);
    print("10: " + pets.containsAll(sub));
    Collections.sort(sub); // In-place sort
    print("sorted subList: " + sub);
    // Order is not important in containsAll():
    print("11: " + pets.containsAll(sub));
    Collections.shuffle(sub, rand); // Mix it up
    print("shuffled subList: " + sub);
    print("12: " + pets.containsAll(sub));
    List<Pet> copy = new ArrayList<Pet>(pets);
    sub = Arrays.asList(pets.get(1), pets.get(4));
    print("sub: " + sub);
    copy.retainAll(sub);
    print("13: " + copy);
    copy = new ArrayList<Pet>(pets); // Get a fresh copy
    copy.remove(2); // Remove by index
    print("14: " + copy);
    copy.removeAll(sub); // Only removes exact objects
    print("15: " + copy);
    copy.set(1, new Mouse()); // Replace an element
    print("16: " + copy);
    copy.addAll(2, sub); // Insert a list in the middle
    print("17: " + copy);
    print("18: " + pets.isEmpty());
    pets.clear(); // Remove all elements
    print("19: " + pets);
    print("20: " + pets.isEmpty());
    pets.addAll(Pets.arrayList(4));
    print("21: " + pets);
    Object[] o = pets.toArray();
    print("22: " + o[3]);
    Pet[] pa = pets.toArray(new Pet[0]);
    print("23: " + pa[3].id());
  }
} /* Output:
1: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug]
2: [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Hamster]
3: true
4: Cymric 2
5: -1
6: false
7: true
8: [Rat, Manx, Mutt, Pug, Cymric, Pug]
9: [Rat, Manx, Mutt, Mouse, Pug, Cymric, Pug]
subList: [Manx, Mutt, Mouse]
10: true
sorted subList: [Manx, Mouse, Mutt]
11: true
shuffled subList: [Mouse, Manx, Mutt]
12: true
sub: [Mouse, Pug]
13: [Mouse, Pug]
14: [Rat, Mouse, Mutt, Pug, Cymric, Pug]
15: [Rat, Mutt, Cymric, Pug]
16: [Rat, Mouse, Cymric, Pug]
17: [Rat, Mouse, Mouse, Pug, Cymric, Pug]
18: false
19: []
20: true
21: [Manx, Cymric, Rat, EgyptianMau]
22: EgyptianMau
23: 14
*///:~

上述例子导入了typeinfo.pets，这里只需要知道：有一个Pet类，以及Pet类的各种子类型；静态的Pets.arrayList()方法将返回一个填充随机选取得Pet对象的lArrayList

你可以用contains()方法来确定某个对象是否在列表中。如果想移除一个对象，可以将对象引用传递给remove()方法。如果有一个对象引用，可以使用indexOf()发现该对象在List中所处位置的索引编号。

确定一个元素是否属于某个List，发现某个元素索引，从List中移除某个元素，都会用到equals()方法。在List中间插入元素是可行的，对于LinkedList来说，列表中间插入和删除是廉价操作，对于ArrayList来说则是昂贵操作。

subList()方法允许从较大的列表中创建一个片段，将其结果传递给这个较大列表的containsAll()方法，自然会得到true。在sub上调用Collections.sort()和Collection.shuffle()方法，不会影响containsAll()结果。

retainAll()是一种有效的交集操作，所产生的行为依赖于equals()方法。removeAll()方法的行为也是基于equals()方法，它将从List中移除在参数List中的所有元素。

set()方法是在指定的索引处（第一个参数），用第二个参数替换整个位置的元素。

对于List，有一个重载的aadAll()方法使得可以在初始的List的中间插入新的列表，而不仅仅只能用Collection的addAll()方法将其追加到表尾。

isEmpty()方法和clear()方法是判断容器是否为空和清除容器中的所有元素。

toArray()方法将任意的Collection转换为一个数组，这是一个重载方法。无参数版本返回的是Object数组，如果向其传递目标类型的数据，它将产生指定类型的数据。

11.6 迭代器

任何容器类，都必须有某种方式可以插入元素并将它们再次取回。对于List，add()是掺入元素的方法之一，而get()是取出元素的方法之一。这里有个缺点：要使用容器，就必须对容器的确切类型编程。初看没事，但是考虑如下情况：如果原本是对着List编码，后来发现，如果能够把相同的代码应用于Set，将会显得非常方便，这是用如何才能不重写代码就可以应用于不同类型的容器？

迭代器的概念就是达成这一目的。迭代器是一个对象，它的工作是遍历并选择序列中的对象，而客户端程序员并不需要知道该序列的底层结构。此外，迭代器又被称为轻量级对象：创建它代价小，因此对于迭代器有各种限制：

1. Iterator只能单向移动
2. 使用方法iterator()要求容器返回一个Iterator。Iterator将准备好返回序列的第一个元素
3. 使用next()获得序列中的下一个元素
4. 使用hasNext()检查序列中是否还有元素
5. 受用remove()将迭代器新近返回的元素删除

示例：

//: holding/SimpleIteration.java
import typeinfo.pets.*;
import java.util.*;

public class SimpleIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.arrayList(12);
    Iterator<Pet> it = pets.iterator();
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
    // A simpler approach, when possible:
    for(Pet p : pets)
      System.out.print(p.id() + ":" + p + " ");
    System.out.println();   
    // An Iterator can also remove elements:
    it = pets.iterator();
    for(int i = 0; i < 6; i++) {
      it.next();
      it.remove();
    }
    System.out.println(pets);
  }
} /* Output:
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster
[Pug, Manx, Cymric, Rat, EgyptianMau, Hamster]
*///:~

11.6.1 ListIterator

ListIterator是一种更强大的Iterator的子类型，它只能用于各种List类的访问。Iterator只能向前移动，但是ListIterator可以双向移动，还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引，并且可以使用set()方法替换它访问过的最后一个元素。可以调用listIterator()方法产生一个指向List开始处的ListIterator，并且还可以通过调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。
示例：

//: holding/ListIteration.java
import typeinfo.pets.*;
import java.util.*;

public class ListIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.arrayList(8);
    ListIterator<Pet> it = pets.listIterator();
    while(it.hasNext())
      System.out.print(it.next() + ", " + it.nextIndex() +
        ", " + it.previousIndex() + "; ");
    System.out.println();
    // Backwards:
    while(it.hasPrevious())
      System.out.print(it.previous().id() + " ");
    System.out.println();
    System.out.println(pets);   
    it = pets.listIterator(3);
    while(it.hasNext()) {
      it.next();
      it.set(Pets.randomPet());
    }
    System.out.println(pets);
  }
} /* Output:
Rat, 1, 0; Manx, 2, 1; Cymric, 3, 2; Mutt, 4, 3; Pug, 5, 4; Cymric, 6, 5; Pug, 7, 6; Manx, 8, 7;
7 6 5 4 3 2 1 0
[Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Manx]
[Rat, Manx, Cymric, Cymric, Rat, EgyptianMau, Hamster, EgyptianMau]
*///:~

11.7 LinkedList

LinkedList也像ArrayList一样实现了基本的List接口，但是它执行某些操作（List中间进行插入和移除）时比ArrayList更高效，在随机访问操作方面更逊一筹。LinkedList还添加了可以使用其用作栈，队列或双端队列的方法。这些方法有些只是名称有些差异，或许只存在些许差异，特别是在Queue中。例如：getFirst()和element()完全一样，它们都返回列表的头（第一个元素），并不移除它，如果List为空，则抛出异常。peek()方法与这两个方式只是稍有差异，他在列表为空的时候返回null。

removeFirst()与remove()一样，移除并返回列表头，如果列表为空抛出异常，poll()稍有差异，列表为空返回null。addFirst()和add()和addLast()相同，它们都将某个元素插入到列表的尾部。
removeLast()移除并返回最后一个元素。

Queue接口是在LinkedList的基础上添加了element(),offer(),peek(),poll()和remove()方法，使其变成一个Queue实现。
示例：

//: holding/LinkedListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;

public class LinkedListFeatures {
  public static void main(String[] args) {
    LinkedList<Pet> pets =
      new LinkedList<Pet>(Pets.arrayList(5));
    print(pets);
    // Identical:
    print("pets.getFirst(): " + pets.getFirst());
    print("pets.element(): " + pets.element());
    // Only differs in empty-list behavior:
    print("pets.peek(): " + pets.peek());
    // Identical; remove and return the first element:
    print("pets.remove(): " + pets.remove());
    print("pets.removeFirst(): " + pets.removeFirst());
    // Only differs in empty-list behavior:
    print("pets.poll(): " + pets.poll());
    print(pets);
    pets.addFirst(new Rat());
    print("After addFirst(): " + pets);
    pets.offer(Pets.randomPet());
    print("After offer(): " + pets);
    pets.add(Pets.randomPet());
    print("After add(): " + pets);
    pets.addLast(new Hamster());
    print("After addLast(): " + pets);
    print("pets.removeLast(): " + pets.removeLast());
  }
} /* Output:
[Rat, Manx, Cymric, Mutt, Pug]
pets.getFirst(): Rat
pets.element(): Rat
pets.peek(): Rat
pets.remove(): Rat
pets.removeFirst(): Manx
pets.poll(): Cymric
[Mutt, Pug]
After addFirst(): [Rat, Mutt, Pug]
After offer(): [Rat, Mutt, Pug, Cymric]
After add(): [Rat, Mutt, Pug, Cymric, Pug]
After addLast(): [Rat, Mutt, Pug, Cymric, Pug, Hamster]
pets.removeLast(): Hamster
*///:~

11.8 stack

”栈“通常是指”先进后出“的容器。有时栈也被称为”叠加栈“，因为最后压入栈中的元素总是第一个弹出。

LinkedList能够直接实现栈的所有功能的方法，因此可以将LinkedList当做栈使用。不过，有时候一个真正的栈更易于理解表述清楚。
示例：

//: net/mindview/util/Stack.java
// Making a stack from a LinkedList.
package net.mindview.util;
import java.util.LinkedList;

public class Stack<T> {
  private LinkedList<T> storage = new LinkedList<T>();
  public void push(T v) { storage.addFirst(v); }
  public T peek() { return storage.getFirst(); }
  public T pop() { return storage.removeFirst(); }
  public boolean empty() { return storage.isEmpty(); }
  public String toString() { return storage.toString(); }
} ///:~

这里通过使用泛型，引入了在栈的类定义中最简单的可行示例。类名之后的<T>表示这是一个参数化类型，其中的类型参数，即类被使用时将会被实际类型替换的参数，即T。stack使用LinkedList实现的，而LinkedList也将告知它将持有T类型对象。push()接受T类型对象，而peek(),pop()将返回T类型对象。peek()方法将提供栈顶元素，但是并不移除，而pop()将移除并返回栈顶元素。

11.9 Set

Set不保存重复的元素。如果你试图将相同对象的多个实例添加到Set中，那么它就会阻止这种重复现象。Set最常用被使用的是测试归属性，可以很容易地查询某个对象是否在某个Set中，通常选择一个HashSet实现，它专门对快速查找进行了优化。

Set具有和Collection完全一样的接口，没有任何额外的功能。实际上Set就是Collection，二者行为不同。Set是基于对象的值来确定归属性的。
HashSet示例：

//: holding/SetOfInteger.java
import java.util.*;

public class SetOfInteger {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Set<Integer> intset = new HashSet<Integer>();
    for(int i = 0; i < 10000; i++)
      intset.add(rand.nextInt(30));
    System.out.println(intset);
  }
} /* Output:
[15, 8, 23, 16, 7, 22, 9, 21, 6, 1, 29, 14, 24, 4, 19, 26, 11, 18, 3, 12, 27, 17, 2, 13, 28, 20, 25, 10, 5, 0]
*///:~

HashSet输出顺序没有规律，因为其使用了散列，使得速度更快。HashSet所维护的顺序与TreeSet和LinkedSet都不同，它们的实现具有不同的元素存储方式。TreeSet将元素存储在红-黑树数据结构中，而HashSet使用的是散列函数。LinkedHashList查询速度快是使用了散列，但是使用了链表来维护元素的插入顺序。
如果相对结果排序，使用TreeSet来代替HashSet。

11.10 Map

通过一个示例来了解一下Map，如测试Random类的随机性，键是Random产生的数字，而值是该数字出现的次数。

//: holding/Statistics.java
// Simple demonstration of HashMap.
import java.util.*;

public class Statistics {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Map<Integer,Integer> m =
      new HashMap<Integer,Integer>();
    for(int i = 0; i < 10000; i++) {
      // Produce a number between 0 and 20:
      int r = rand.nextInt(20);
      Integer freq = m.get(r);
      m.put(r, freq == null ? 1 : freq + 1);
    }
    System.out.println(m);
  }
} /* Output:
{15=497, 4=481, 19=464, 8=468, 11=531, 16=533, 18=478, 3=508, 7=471, 12=521, 17=509, 2=489, 13=506, 9=549, 6=519, 1=502, 14=477, 10=513, 5=503, 0=481}
*///:~

如果键不在容器中，get()方法将返回null，否则get()方法将产生与该键关联的Integer值，然后这个值被递增。
关于Map，比较常用的是使用containsKey()和containsvalue()来查看他是否包含某个键或某个值。
示例：

//: holding/PetMap.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;

public class PetMap {
  public static void main(String[] args) {
    Map<String,Pet> petMap = new HashMap<String,Pet>();
    petMap.put("My Cat", new Cat("Molly"));
    petMap.put("My Dog", new Dog("Ginger"));
    petMap.put("My Hamster", new Hamster("Bosco"));
    print(petMap);
    Pet dog = petMap.get("My Dog");
    print(dog);
    print(petMap.containsKey("My Dog"));
    print(petMap.containsValue(dog));
  }
} /* Output:
{My Cat=Cat Molly, My Hamster=Hamster Bosco, My Dog=Dog Ginger}
Dog Ginger
true
true
*///:~

Map可以很容易扩展到多维情况上，例如跟踪一个拥有多个宠物的人，可以是Map<Person,List<Pet>>

11.11 Queue

队列是一个典型的先进先出的容器，即从容器的一端放入事物，从另一端取出，事物放入的顺序和取出的顺序是相同的。队列在并发编程中特别重要。
LinkedList提供了方法支持队列的行为，并且实现了队列的接口，因此LinkedList可以是Queue的一种实现。
队列使用示例：

//: holding/QueueDemo.java
// Upcasting to a Queue from a LinkedList.
import java.util.*;

public class QueueDemo {
  public static void printQ(Queue queue) {
    while(queue.peek() != null)
      System.out.print(queue.remove() + " ");
    System.out.println();
  }
  public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<Integer>();
    Random rand = new Random(47);
    for(int i = 0; i < 10; i++)
      queue.offer(rand.nextInt(i + 10));
    printQ(queue);
    Queue<Character> qc = new LinkedList<Character>();
    for(char c : "Brontosaurus".toCharArray())
      qc.offer(c);
    printQ(qc);
  }
} /* Output:
8 1 1 1 5 14 3 1 0 1
B r o n t o s a u r u s
*///:~

offer()方法在允许的情况下，将一个元素插入到队尾，或者返回false。peek()和element()都将在不移除的情况下返回队头，但是peek()方法在队列为空的时候返回null，而element()会抛出异常。****poll()和remove()方法都是移除并返回队列头部，poll()在队列为空返回null，后者抛出异常。、

11.11.1 PriorityQueue

先进先出描述了最典型的队列规则。队列规则是指给定一组队列中的元素情况下，确定下一个弹出队列的元素规则，先进先出声明的是下一个元素应该是等待时间最长的元素。

优先级队列声明下一个弹出元素是最需要的元素（具有最高优先级）。某些消息比其他消息更重要，应该更快得到处理，那么它们的处理与它们何时到达无关。PriorityQueue添加到了Java SE5中，提供了这种行为的自动实现。

在PriorityQueue中调用offer()插入对象，会在队列中被排序，**默认是自然顺序。可以通过自己提供的Comparator来修改这一顺序。**PriorityQueue确保使用peek(),remove()和poll()方法是获取的元素是队列中优先级最高的元素。
示例：

//: holding/PriorityQueueDemo.java
import java.util.*;

public class PriorityQueueDemo {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue =
      new PriorityQueue<Integer>();
    Random rand = new Random(47);
    for(int i = 0; i < 10; i++)
      priorityQueue.offer(rand.nextInt(i + 10));
    QueueDemo.printQ(priorityQueue);

    List<Integer> ints = Arrays.asList(25, 22, 20,
      18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);
    priorityQueue = new PriorityQueue<Integer>(ints);
    QueueDemo.printQ(priorityQueue);
    priorityQueue = new PriorityQueue<Integer>(
        ints.size(), Collections.reverseOrder());
    priorityQueue.addAll(ints);
    QueueDemo.printQ(priorityQueue);

    String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
    List<String> strings = Arrays.asList(fact.split(""));
    PriorityQueue<String> stringPQ =
      new PriorityQueue<String>(strings);
    QueueDemo.printQ(stringPQ);
    stringPQ = new PriorityQueue<String>(
      strings.size(), Collections.reverseOrder());
    stringPQ.addAll(strings);
    QueueDemo.printQ(stringPQ);

    Set<Character> charSet = new HashSet<Character>();
    for(char c : fact.toCharArray())
      charSet.add(c); // Autoboxing
    PriorityQueue<Character> characterPQ =
      new PriorityQueue<Character>(charSet);
    QueueDemo.printQ(characterPQ);
  }
} /* Output:
0 1 1 1 1 1 3 5 8 14
1 1 2 3 3 9 9 14 14 18 18 20 21 22 23 25 25
25 25 23 22 21 20 18 18 14 14 9 9 3 3 2 1 1
       A A B C C C D D E E E F H H I I L N N O O O O S S S T T U U U W
W U U U T T S S S O O O O N N L I I H H F E E E D D C C C B A A
  A B C D E F H I L N O S T U W
*///:~

重复是允许的，最小值拥有最高的优先级。如果是String，空格也可以算作值，且比字母优先级高。

11.12 Collection和Iterator

Collection是描述所有序列容器共同的根接口。。。。。。。。。

11.13 Foreach与迭代器

foreach语法主要用于数组，它也可以应用于任何Collection对象。
示例：

//: holding/ForEachCollections.java
// All collections work with foreach.
import java.util.*;

public class ForEachCollections {
  public static void main(String[] args) {
    Collection<String> cs = new LinkedList<String>();
    Collections.addAll(cs,
      "Take the long way home".split(" "));
    for(String s : cs)
      System.out.print("'" + s + "' ");
  }
} /* Output:
'Take' 'the' 'long' 'way' 'home'
*///:~

之所以能工作，是因为Java SE5 引入了新的被称为Iterable接口，该接口包含了一个能够产生Iterator的iterator()方法，并且Iterator接口被foreach用来在序列中移动。因此，如果创建了任何实现Iterable的类，都可以将它用于foreach语句中。

//: holding/IterableClass.java
// Anything Iterable works with foreach.
import java.util.*;

public class IterableClass implements Iterable<String> {
  protected String[] words = ("And that is how " +
    "we know the Earth to be banana-shaped.").split(" ");
  public Iterator<String> iterator() {
    return new Iterator<String>() {
      private int index = 0;
      public boolean hasNext() {
        return index < words.length;
      }
      public String next() { return words[index++]; }
      public void remove() { // Not implemented
        throw new UnsupportedOperationException();
      }
    };
  } 
  public static void main(String[] args) {
    for(String s : new IterableClass())
      System.out.print(s + " ");
  }
} /* Output:
And that is how we know the Earth to be banana-shaped.
*///:~

在Java SE5中，大量的类都是Iterator类型，主要包括所有的Collection类（不包括Map）。foreach语句可以用于数组或其他任何Iterable，但是并不意味着数组肯定是一个Iterable，任何自动包装也不会产生。
示例：

//: holding/ArrayIsNotIterable.java
import java.util.*;

public class ArrayIsNotIterable {
  static <T> void test(Iterable<T> ib) {
    for(T t : ib)
      System.out.print(t + " ");
  }
  public static void main(String[] args) {
    test(Arrays.asList(1, 2, 3));
    String[] strings = { "A", "B", "C" };
    // An array works in foreach, but it's not Iterable:
    //! test(strings);
    // You must explicitly convert it to an Iterable:
    test(Arrays.asList(strings));
  }
} /* Output:
1 2 3 A B C
*///:~