キュー構造をJavaで実装してジェネリック型を理解する：【改訂版】Eclipseではじめるプログラミング（19）（3/3 ページ）

» 2010年10月14日 00時00分公開

[小山博史，株式会社ガリレオ]

【第3改訂】Java APIのジェネリック型も使って実装

　ところで、Sample03.Queueクラスで、なぜ「Object[] values = new Object[SIZE+1];」を「T[] values = new T[SIZE+1];」としないのか疑問に思った読者もいるのではないでしょうか。

ジェネリックスでできないこと

　実は、ジェネリック型の中では、型変数Tのインスタンス生成や、型変数を指定した配列のインスタンス生成ができません。また、staticフィールドやstaticメソッド内、static初期化子でも型変数は使用できませんやstaticメソッド内、static初期化子でも型変数は使用できません。

　これは、クラスとして生成されるのはSample03.Queueだけであり、Sample03.Queue<Long>やSample03.Queue<Integer>のように指定しても、それぞれのクラスが生成されるわけではないことに関係しています。

　「new Sample03.Queue<Long>()」のように生成されたインスタンスは、Sample03.Queue型であり、「Sample03.Queue<Long>として生成された」という情報は「削除（イレイズ、erase）」されてしまうのです。これはコンパイル時に行われます。

　詳細はここでは説明しませんが、クラスファイルとしてはSample03.Queueに対応するものだけが生成され、Sample03.Queue<Long>などに対応するクラスファイルは生成されない点は覚えておいてください。

配列ではなくjava.util.ArrayListを使ってみる

　Sample03.Queueクラスでは、ダウンキャストの警告が消えなかったのですが、これは結局Object型の配列を使っている点に問題があります。そこで、配列ではなくjava.util.ArrayListを使ってみましょう。

　その場合のコードは、次のようになります。これまでの処理をあまり変更しないように実装しています。

package sample19;
 
import java.util.ArrayList;
 
public class Sample05 {
    static class Queue<T> {
        final int SIZE = 5;
        private ArrayList<T> values = new ArrayList<T>();
        private int head = 0;
        private int tail = 0;
        Queue() {
            for (int i=0 ; i<SIZE+1 ; i++) {
                values.add(null);
            }
        }
        boolean enqueue(T data) {
            if (data == null) return false;
            if (((tail + 1) % values.size()) == head) {
                return false;
            }
            values.set(tail++, data);
            tail = tail % values.size();
            return true;
        }
        T dequeue() {
            T data = null;
            if (tail != head) {
                data = values.get(head++);
                head = head % values.size();
            }
            return data;
        }
        boolean isEmpty() {
            return (tail == head);
        }
    }
 
    public static void main(String[] args) {
// 略
    }
}

sample19/Sample05.java

　ここでのポイントは、java.util.ArrayListはジェネリック型なので、「Queueの型変数『T』を、そのままjava.util.ArrayListの型引数として指定している」点です。

　また、java.util.ArrayList型のvalues変数を配列のように使いたいので、Queueクラスのコンストラクタで必要な要素数分nullを追加して初期化します。

　後は、次のように置き換えています。

「values.length」を「values.size()」へ
「values[tail++] = data;」を「values.set(tail++, data);」へ
「data = values[head++];」を「 data = values.get(head++);」へ

　これにより、コードから警告が消えて、これまでと同じ結果が出るプログラムとなります。

java.util.Listインターフェイスのメソッドで、もっと簡単に

　さて、ここまでは配列によるQueueクラスを実装し、Sample05.Queueクラスでは配列と同等の機能を持つクラスとしてjava.util.ArrayListクラスを利用しました。ここで、java.util.Listインターフェイスのメソッドをうまく使うと、Sample05.Queueクラスは、もっと簡単に実装ができます。java.util.Listとjava.util.LinkedListを使って実装してみましょう。

　java.util.Listインターフェイスでは、enqueueメソッドの実装にaddメソッドが使えます。また、dequeueメソッドの実装にremoveメソッドが使えます。そのため、要素数の管理に必要な処理だけ追加して、次のように実装できます。随分とすっきりとしました。

package sample19;
 
import java.util.LinkedList;
import java.util.List;
 
public class Sample06 {
    static class Queue<T> {
        final int SIZE = 5;
        private List<T> values = new LinkedList<T>();
        boolean enqueue(T data) {
            if (data == null) return false;
            if (values.size() == SIZE) {
                return false;
            }
            values.add(data);
            return true;
        }
        T dequeue() {
            T data = null;
            if (values.size() != 0) {
                data = values.remove(0);
            }
            return data;
        }
        boolean isEmpty() {
            return (values.size() == 0);
        }
    }
 
    public static void main(String[] args) {
// 略
    }
}

sample19/Sample06.java

実は、java.util.Queueインターフェイスがある

　さて、ジェネリックスについて説明をするために独自にQueueクラスを実装する方法について説明をしてきましたが、実はJava APIで提供されているjava.util.Queueインターフェイスがあります。こちらも使ってみましょう。

java.util.Queueインターフェイスと独自Queueクラスの違い

　Java APIでは、java.util.Queueインターフェイスが用意されていて、これを実装するクラスがいくつかあります。java.util.Queueインターフェイスでは、似たようなメソッドがいくつか宣言されているので、用途に応じてどれを使うか決めましょう。

　今回の独自Queueクラスで用意したenqueueメソッドとdequeueメソッドに対応するメソッドは、Java APIではofferメソッドとpollメソッドです。


	操作	独自Queue	java.util.Queue
	挿入	enqueue(e)	offer(e)
	削除	dequeue()	poll()
表　java.util.Queueインターフェイスと独自Queueクラスの違い

java.util.Queueインターフェイスでサンプルを改訂

　これを使って、ここまでのサンプルと同じ動作をするようにコーディングすると、次のようになります。ここでは、java.util.Queueインターフェイスを実装するクラスとして、java.util.ArrayDequeクラスを使っています。

package sample19;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class Sample07 {
    public static void main(String[] args) {
        Queue<Long> q = new ArrayDeque<Long>();
        q.offer(1L);
        q.offer(2L);
        q.offer(3L);
        q.offer(4L);
        q.offer(5L);
        q.offer(6L);
        System.out.println(q.poll());
        q.offer(7L);
        while (!q.isEmpty()) {
            System.out.print(q.poll()+",");
        }
        System.out.println("");
    }
}

sample19/Sample07.java

「ワイルドカード」でジェネリックス機能を生かす

　ジェネリックス機能を使うに当たって、「ワイルドカード（wild card）」についても知っておく必要があります。

さまざまな型を受け取れるメソッドを、どのように定義すればいいか

　次のようなプログラムを作成してみましょう。

package sample19;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class Sample08 {
    void print(Queue q) {
        while (!q.isEmpty()) {
            System.out.print(q.poll()+",");
        }
        System.out.println("");
    }
    void exec() {
        Queue<Long> q0 = new ArrayDeque<Long>();
        q0.offer(1L);
        q0.offer(2L);
        q0.offer(3L);
        print(q0);
        Queue<Integer> q1 = new ArrayDeque<Integer>();
        q1.offer(1);
        q1.offer(2);
        q1.offer(3);
        print(q1);
    }
    public static void main(String[] args) {
        Sample08 app = new Sample08();
        app.exec();
    }
}

sample19/Sample08.java

　Queueオブジェクトを受け取って、そこに含まれる値を出力する「print」メソッドを用意し、使っています。処理自体は単純なので、説明することもありません。ここでは、Queue<Long>型の「q0」やQueue<Integer>型の「q1」を受け取ることができるメソッドを、どのように定義すればいいかを考えてもらいたいのです。

　Sample08クラスでは、「原型」を使っているためprintメソッドに警告が出ます。「パラメータ化した型にする必要がある」という警告が出るので、Long型やInteger型の共通のスーパークラスであるObject型を使ってみたら良さそうな気がします。つまり、「void print(Queue<Object> q) {」としてみるのです。

　ところが、そうすると、「print(q0);」と「print(q1);」でエラーになります。これは、Queue<Object>はQueue<Long>でもないですし、Queue<Integer>でもないからです。

ジェネリックスでのワイルドカード

　こんなときは、どんな型か具体的な指定はしないが何かの型が指定されるということをコンパイラへ指示するために、ワイルドカードを使います。ジェネリックスでのワイルドカードは「?」を使います。次のように指定して、printメソッドはパラメータ化されたQueueオブジェクトをメソッドの引数として受け取ることを宣言します。

package sample19;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class Sample09 {
    void print(Queue<?> q) { // ワイルドカードを指定
        while (!q.isEmpty()) {
            System.out.print(q.poll()+",");
        }
        System.out.println("");
    }
// 略
}

sample19/Sample09.java

「非境界ワイルドカード」と「境界ワイルドカード」

　「?」だけだと「非境界ワイルドカード（unbounded wildcard）」で、「どんな型でパラメータ化されていてもいい」ということになります。ある型をimplementsまたはextendsした型でパラメータ化されている場合だけ使えるメソッドとしたいこともあるでしょう。そんな場合は、「境界ワイルドカード（bounded wildcard）」を使います。例えば、「void print(Queue<? extends Number> q)」とすれば、q0もq1も渡せますが、「void print(Queue<? extends Integer> q)」とすると、q0は渡せなくなります。

理解するには実装あるのみだが利用はAPIで

　今回は、キューについて説明し、それを実装するクラスをいくつか作成してみましたが、いかがでしたか。さまざまなデータ型に対して、同じ処理をしたい場合には、ジェネリック型を使って実装すると、効率良くプログラミングができることが理解できたでしょうか。

　また、Java APIでは、リストやスタック、キューといった有名でよく研究されたデータ構造を表現するデータ型について、ジェネリック型を使って汎用的に実装されています。これらを使うことによって、最初から自分で実装するよりも楽に高度なプログラムを作成できます。

　こういったデータ構造の実装について理解するためにはサンプルプログラムを作成したりする必要がありますが、実際の現場では、Java APIで用意されているインターフェイスやクラスを利用するようにしましょう。

　ジェネリックスは、今回説明した以外にも、いくつかの文法事項があります。ジェネリック型を自分で定義できるようになるには、今回説明した内容だけでは足りませんが、ジェネリック型を利用するために必要な最低限の基本については説明しました。型について安全なプログラミングをするために、積極的に利用するようにしてください。

　次回は「拡張for文」について説明する予定です。今回作ったサンプルのソースコードはこちらからダウンロードできます。