11. 新たに追加されたコレクション

2006.05.26　株式会社四次元データ　宮澤了祐

11.1. Queueインターフェイス

JDK5.0よりキュー形式のデータ構造が追加されました。 今までもjava.util.Listを使って、FIFO（First-In-First-Out）形式のデータ入出力を行うことは可能でした。 java.util.Queueインタフェースには、データの追加・削除・監査を行うメソッドが追加されています。

public boolean offer(Object element)
public Object remove()
public Object poll()
public Object element()
public Object peek()

offer()メソッドは可能であれば要素を追加し、キューがいっぱいなどで追加が不可能な場合、falseを返します。 element()メソッドは、キューの先頭を取得しますが削除しません。 キューが空であれば、java.util.NoSuchElementExceptionを投げます。

peek()メソッドもelement()メソッドと同様に、キューの先頭を取得しますが削除しません。 element()メソッドと違い、空であればnullが返ってきます。 poll()メソッド及びremove()メソッドは、キューの先頭を取得し、さらに削除します。 delete()メソッドは、削除対象が空の場合にはNoSuchElementExceptionを投げますが、 poll()メソッドはnullを返します。

以下の実装があります。

• java.util.AbstractQueue
  　　Queueのスケルトン実装です。
• java.util.LinkedList
  　　Listの実装の一つであるLinkedListがQueueを実装するようになりました。
• java.util.PriorityQueue
  　　優先度を指定することで要素を整列するQueue実装です。

以下はLinkedListを用いた例です。

Queue<Integer> queue = new LinkedList();
queue.offer(1);
queue.offer(2);
queue.offer(3);

Integer i;
while((i = queue.poll()) != null) {
    System.out.println(i);
}

11.2. PriorityQueue

PriorityQueueは挿入されたオブジェクトを指定した優先順位で並べ替えるキューです。 二つのオブジェクトを比較するメソッドcompare()を持つjava.util.Comparatorインターフェイスを実装し、 PriorityQueueのコンストラクタに渡すことで、任意のオブジェクトの優先順位を設定することが出来ます。

例えば二つの文字列を渡した際に、文字数を比較するComparatorを作成すると次のようになります。

import java.util.Comparator;

public class MyComparator implements Comparator {

    public int compare(Object obj1, Object obj2) {
        
        String str1 = (String)obj1;
        String str2 = (String)obj2;
        
        if(str1.length() > str1.length()) {
            return 1;
        } else if(str1.length() < str2.length()) {
            return -1;
        } else{
            return 0;
        }

    }

}

Comparatorは、第一引数より第二引数の方が大きい場合負の数を、小さい場合は正の数を、等しい場合は0を返します。

このComparatorを利用して文字列を長い順に並べ替えるPriorityQueueを作成します。

public static void main(String[] args) {
    Queue queue = new PriorityQueue(1, new MyComparator());
    
    String[] obj = {"あいうえお", "良い天気ですね。", "こんにちは", "やあ", "ばいばい"};
    
    for(int i = 0; i < obj.length; i++) {
        queue.add(obj[i]);
    }
    
    while(true) {
        String str = (String)queue.poll();
        
        if(str == null) {
            break;
        }
        
        System.out.println(str);
    }
}

ここではComparatorを指定するコンストラクタを使用しています。

Queue queue = new PriorityQueue(1, new MyComparator());

第一引数で初期容量を指定します。初期容量より多くの要素を追加しようとした場合、自動的に容量は拡張されます。

次のように出力されます。

良い天気ですね。
あいうえお
こんにちは
ばいばい
やあ

またIteratorはこの優先度に基づいた並べ替えがされていないので、 もしIteratorを使用して優先度順に並べ替える場合次のようにする必要があります。

Arrays.sort(queue.toArray(), new MyComparator());
        
Iterator itr = queue.iterator();
while(itr.hasNext()) {
    String str = (String)itr.next();
    System.out.println(str);
}

Comparatorを指定しない場合はPriorityQueueに追加するオブジェクトはComparableインターフェイスを実装しているオブジェクトに限ります。