Azi---向盖茨学习，52岁退休

在计算机学科中，基础数据结构之一 — 是Queue。你会想起Queue是一种数据结构，在它里边的元素可以按照添加它们的相同顺序被移除。在以前的Java版本中，这中FIFO（先进先出）数据结构很不幸被忽略了。随着Java1.5（也叫Tiger）的出现，对Queue支持第一次成为固有特性。 

过去在没有Queue的情况下如何管理？ 

在Java 1.5以前，通常的实现方式是使用java.util.List集合来模仿Queue。Queue的概念通过把对象添加（称为enqueuing的操作）到List的尾部（即Queue的后部）并通过从List的头部（即Queue的前部）提取对象而从List中移除（称为dequeuing的操作）来模拟。下面代码显示了你以前可能做法。 


代码:
import java.util.Enumeration; 
import java.util.LinkedList; 
import java.util.Vector; 

public class QueueEmulate 
{ 
     private LinkedList queueMembers; 
     public Object enqueue(Object element) 
     { 
          queueMembers.add (element); 
          return element; 
     } 

     public Object dequeue() 
     { 
          return queueMembers.removeFirst(); 
     } 
}


现在我们有了Queue 

Java 1.5在java.util包中新添加了Queue接口，下面代码中使用到它（从sample code的SimpleQueueUsageExample.java截取）。注意，在Java 1.5中，java.util.LinkedList被用来实现java.util.Queue，如同java.util.List接口。也要注意我是如何显式地声明我的只包含字符串的Queue－－－使用 泛型（如果需要深入了解泛型，请参阅"J2SE 1.5: Java's Evolution Continues"）。这样使我省却了当从Queue中提取它们时不得不进行对象造型的痛苦。 


代码:
Queue myQueue = new LinkedList(); 
myQueue.add("Add Me"); 
myQueue.add("Add Me Too"); 
String enqueued = myQueue.remove();


你可以看到LinkedList类的add和remove方法被分别用于执行enqueuing和dequeuing操作。实际上没有更好的可用方法；Queue接口提供了新的offer和poll方法，如下显示（截取自SimpleQueueUsageExamplePreferred）： 


代码:
Queue myQueue = new LinkedList(); 
boolean offerSuccess; 
// offer method tries to enqueue.  
// A boolean is returned telling you if the 
// attempt to add to the queue was successful or not 
offerSuccess=myQueue.offer("Add Me"); 
offerSuccess=myQueue.offer("Add Me Too"); 
// peek at the head of the queue, but don't grab it 
Object pull = myQueue.peek(); 
String enqueued = null; 
// grab the head of the queue 
if (pull!=null) enqueued = myQueue.poll(); 
System.out.println(enqueued);

如果你的Queue有固定长度限制（常常是这种情形），使用add方法向Queue中添加内容，将导致抛出一个非检查异常。当你编译SimpleQueueUsageExample的代码时，编译器将会就此问题发出警告。相反，当新的offer方法试图添加时，如果一切正常则会返回TRUE，否则，返回FALSE。同样地，如果你试图使用remove方法对一个空Queue操作时，也将导致一个非检查异常。 

你也可以使用poll方法去从Queue中提取元素。如果在Queue中没有元素存在，poll方法将会返回一个null（即不会抛出异常）。在某些情况下，你可能不想提取头部的元素而只是想看一下。Queue接口提供了一个peek方法来做这样的事情。如果你正在处理一个空Queue，peek方法返回null。象add－offer和remove－poll关系一样，还有peek－element关系。在Queue为空的情形下，element方法抛出一个非检查异常。但如果在Queue中有元素，peek方法允许你查看一下第一个元素而无需真的把他从Queue中取出来。peek方法的用法在SimpleQueueUsageExamplePreferred类中有示例。 


AbstractQueue类 

如你所见，java.util.LinkedList类实现了java.util.Queue接口，同样，AbstractQueue也是这样。AbstractQueue 类实现了java.util接口的一些方法（因此在它的名字中包含abstract）。而AbstractQueue将重点放在了实现offer，poll和peek方法上。另外使用一些已经提供的具体实现。 

PriorityQueue类 

在PriorityQueue中，当你添加元素到Queue中时，实现了自动排序。根据你使用的PriorityQueue的不同构造器，Queue元素的顺序要么基于他们的自然顺序要么通过PriorirtyQueue构造器传入的Comparator来确定。下面的代码示例了PirorityQueue类的使用方法。在Queue的前边是字符串"Alabama"－由于元素在PriorityQueue中是按自然顺序排列的（此例中是按字母表顺序）。 


代码:
PriorityQueue priorityQueue = new PriorityQueue(); 
priorityQueue.offer("Texas"); 
priorityQueue.offer("Alabama"); 
priorityQueue.offer("California"); 
priorityQueue.offer("Rhode Island"); 
int queueSize = priorityQueue.size(); 
for (int i =0; i< queueSize; i++) 
{ 
     System.out.println(priorityQueue.poll()); 
}


执行结果如下： 

Alabama 
California 
Rhode Island 
Texas 

Queue各项按照自然顺序－字母顺序－来排列。 

如上提到的，你可以创建你自己的Comparator类并提供给PirorityQueue。如此，你可以定义你自己的排序方式。在PriorityQueueComparatorUsageExample 类中可找到此方式，在其中使用了一个名为State的助手类。如你在下边看到的，在类定义中，State只简单地包含了一个名字和人口。 

代码:
private String name; 
private int population; 

public State(String name, int population) 
{ 
     super(); 
     this.name = name; 
     this.population = population; 
}    

public String getName() 
{ 
     return this.name; 
} 

public int getPopulation() 
{ 
     return this.population; 
} 
public String toString() 
{ 
     return getName() + " - " + getPopulation(); 
}

在PriorityQueueComparatorUsageExample中，Queue使用了java.util.Comparator的自定义实现来定义排列顺序（如下）。 


代码:
PriorityQueue priorityQueue = 
     new PriorityQueue(6, new Comparator() 
{ 
     public int compare(State a, State b) 
     { 
       System.out.println("Comparing Populations"); 
       int populationA = a.getPopulation(); 
       int populationB = b.getPopulation(); 
       if (populationB>populationA) 
            return 1; 
       else if (populationB