队列：一个被遗失的java.util类
标准java包 java.util 的出现,带来了大量有用的数据结构（像堆栈Stack，链接表LinkedList，哈希集HashSet和树型集合TreeSet）.但很遗憾的是，队列类在这个标准包中没有被实现。在这篇文章中我们讨论三种方法来实现队列类。
堆栈与队列
堆栈是一种只能对它顶端的元素进行操作的数据结构，对于计算机的堆栈，就象堆叠在一起的盘子器皿，你可以在它上面添加一个元素（或者说添加一个盘子），也可以删除一个元素（拿走一个盘子）。这中操作行为就称之为LIFO(后进先出)。相比之下，队列就是按元素进入的顺序进行删除操作。 通常我们称之为FIFO(先进先出).
堆栈的两个基本操作如下：
push:将一个新的元素推入到堆栈的顶部
pop: 移除并返回堆栈顶部的元素。如果堆栈为空，这个操作可能会引发一个异常。
a.含有四个元素的堆栈 b. pop操作执行后的堆栈
图1:堆栈类的Pop操作。
图1.a 中的堆栈含有四个元素，棕色的元素为堆栈顶部的元素，图1.b 表明同样的一个堆栈，pop操作执行后，棕色的元素已经被移除同时绿色的元素变成了堆栈的顶部元素。
下面是队列的两个基本操作：
Enqueue: 在队列的尾部插入一个新元素
Dequeue: 移除队列头部元素并返回它，如果队列为空，这个操作可能会引发一个异常。
EmptyQueueException 异常
这个异常被队列Queue类的方法抛出以表明队列Queue为空。这个异常将在下面讨论的三个实现方法中用到.
public class EmptyQueueException extends RuntimeException
{
public EmptyQueueException() { }
}
第一种方法：
第一个实现方法类似于对java.util.Stack堆栈类的实现。在实现Queue1.class时，将扩展java.util.Vector 类。借助一些函数操作，可以将Vector等同于队列对待。
public class Queue1 extends Vector
{
public Object enqueue (Object element)
{
addElement (element);
return element;
}
public Object dequeue ()
{
int len = size();
if (len == 0)
throw new EmptyQueueException();
Object obj = elementAt(0);
removeElementAt (0);
return obj;
}
}
enqueue 方法使用了继承来的addElement 方法将一个对象添加到向量Vector后面，dequeue 方法使用一个继承来的removeElementAt 方法移除存放在Vector中的第一个对象。实际中removeElementAt方法移除Vector中的第一个元素时还要执行一些其它额外的任务。Vector中剩余其它的元素肯定要向上移动一个位置，请看图2
需要注意的是这个操作的执行，存在一个性能上的问题，尤其是在元素数量很大的队列当中。图2演示了每次调用dequeue方法将移除向量Vector的第一个元素，同时导致剩余其他的向量Vector的元素向上移动了一个位置.但这对于堆栈stack不存在这个问题，每次调用pop方法将移除向量Vector的的最后一个元素，因此其他剩余的元素就没有必要再移动了(图1)。换句话说，这个实现方法虽然能很有效地实现堆栈stack类，但对于队列Queue类的实现就显的力不从心了。
a.含有四个元素的队列Queue b.dequeue 操作执行后的队列
图2第一次执行Dequeue操作(其它剩余的元素已经全部向上移动了一个位置。)
未完待续
Translated by windowsDNA 2004/01/08
