解读java.util.Queue - 向比尔盖茨学习 - JavaEye技术网站

java5中对队列的实现

解读java.util.Queue

文章分类:Java编程

在计算机学科中，基础数据结构之一 — 是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

解读java.util.Queue - 向比尔盖茨学习 - JavaEye技术网站