MSDN.NET摘录

Queue：java.util缺失的类

                                      

Queue：java.util缺失的类。

 

原作者：Yasser EL-Manzalawy

 

标准Java包java.util中包含了一组很实用的数据结构类，例如栈（Stack）、链表（LinkedList）、散列集（HashSet）和树（TreeSet）。不幸的是，这个包里面并没有实现Queue类。在这篇文章中，我们将要讨论实现Queue类的三种途径。

栈与队列

　　栈是一种使人只能访问顶端元素的数据结构。计算机的栈，就像一摞盘子，你只能把盘子放到最上方，也只能从最上边取出盘子。这种行为叫做后进先出（LIFO：Last In, First Out）。相比较之下，Queue是一种使人只能按照添加的顺序访问元素的数据结构，它的行为通常叫做先进先出（FIFO：First In, First Out）。

栈有两种基本操作：
　　入栈（Push）：向栈的顶端加入新的元素。
　　出栈（Pop）：删除栈顶端的元素，并将其返回；如果栈是空的，这个操作会抛出异常。

队列也有两种基本操作：
　　入列（Enqueue）：在队列的尾部加入新的元素。
　　出列（Dequeue）：删除队列首部的元素，并将其返回；如果队列是空的，这个操作会抛出异常。

EmptyQueueException

　　这个异常由Queue类的方法抛出，表明队列是空的；下面三种实现的途径都会用到这个异常。

public class EmptyQueueException {
　　public EmptyQueueException() {
　　}
}

 

第一种途径：

　　第一种途径与实现java.tuil.Stack类的相似。在这种实现里，Queue1类扩展了java.util.Vector类，提供操作以允许向量类作为一个队列来处理。

public class Queue1 extends java.util.Vector {
　　public Object enqueue(Object o) {
　　　　addElement(o);
　　　　return o;
    }

　　public Object dequeue() {
　　　　if (size() == 0)
　　　　　　throw new EmptyQueueException();
　　　　Object o = elementAt(0);
　　　　removeElementAt(0);
　　　　return o;
　　}
}

　　入列方法（enqueue）使用了继承来的addElement方法，将一个元素添加到向量的尾部。出列方法（dequeue）使用了继承来的removeElementAt方法，删除向量中保存的第一个元素。实际上将向量顶部的元素删除掉，需要一个额外的步骤，这个步骤由removeElementAt方法完成：向量中余下的元素都向前移动一个位置。

　　需要注意的是，这种实现造成了性能问题，特别是队列元素很多的时候。栈（Stack）类的实现则不同，每次调用出栈（pop）方法的时候，向量的最后一个元素被删除，因此没必要移动余下的元素。换句话说，这个途径适合实现栈（Stack）类，但不适合实现队列（Queue）类。

第二种途径：

　　这种途径致力于克服上面提到的性能问题，在LinkedList类之上创建Queue类：因为在链表中进行删除第一个元素的操作不会导致余下元素的移动。

public class Queue2 extends java.util.LinkedList {
　　public Object enqueue(Object o) {
　　　　add(o);
　　　　return o;
　　}

　　public Object dequeue() {
　　　　if (size() == 0)
　　　　　　throw new EmptyQueueException();
　　　　return removeFirst();
　　}
}

　　这种途径中，继承带来了问题。Queue2的用户可以调用继承来的方法，例如addFirst或者getLast等，这会导致Queue类不期望的行为。

第三种途径：

　　这种途径使用对象组合来取代继承。通常情况下，对象组合比继承更好用，因为组合可以提供更小并且更专用的类，以及更小的继承树。多数设计者过度使用继承，导致了巨大的、难以维护的继承树。基于对象组合的设计，会有较少的类、较多的对象。（原文：A design based on object composition will have fewer classes, but more objects.）

public class Queue {
　　private java.util.LinkedList items;

　　public Object enqueue(Object o) {
　　　　items.add(o);
　　　　return o;
　　}

　　public Object dequeue() {
　　　　if (items.size() == 0)
　　　　　　throw new EmptyQueueException();
　　　　return items.removeFirst();
　　}
}

　　这个实现生成了一个强力而又专一的Queue类。当然，开发者还需要显式的编码所有需要的接口（例如size，empty，indexOf等）。

【作者: 胡传魁】【访问统计:】【2006年05月19日 星期五 10:16】【注册】【打印】