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

安全なままコレクションフレームワークを利用するために

　今回は、「ジェネリックス（Generics）」について説明します。

　Javaでは、すべてのクラスはjava.lang.Object型から派生しているので、どのオブジェクトもObject型として扱えば、ある処理をさまざまなデータ型に対して適用できます。

　ただし、この場合は型について安全であることを保証するために、自分でチェックコードを記述したりキャストをする必要があります。これまでの連載では、java.util.Listのような「java.util.Collection」インターフェイスを実装した、いわゆる「コレクションフレームワーク」を利用する際には、Object型としてデータを挿入し、データを取り出したときは、前回の「強く型付けされているJavaの理解に必修の“型変換”」で解説した「ダウンキャスト」を行うなどしていました。

　ジェネリックスを理解して使えるようになると、そういったコードを記述しなくても済むようになります。非常に便利な機能ですし、型について安全なままコレクションフレームワークを利用するには必須の機能ですから、ぜひ使いこなせるようになりましょう。

　EclipseでJavaプログラミングを始める準備がまだの方は、連載第1回の「Eclipse 3.4で超簡単Javaプログラミング基礎入門」で準備をしておいてください。

知っていますか？ データ構造「キュー」？

　ジェネリックスについて理解するために、「キュー（Queue、待ち行列）」といわれるデータ構造を実装してみましょう。キューを使うと、リクエストを受け付けた順番に実行するプログラムを簡単に実装できるようになります。プログラマなら、ぜひ理解しておきたい知識です。

キューの使いどころ

　Webサービスのプラットフォームとなるソフトウェアなどでは、「ユーザーが利用するWebブラウザからのリクエストを受け付けて、受け付けた順番に処理を実行してレスポンスを返す」といった処理が必要です。

　またGUIプログラムのプラットフォームとなるソフトウェアでは、ユーザーが発生するマウスイベントやキー入力イベントを順番に受け付けて、受け付けた順番に実行するといった処理が必要です。そういった場合に、キューが利用できます。

キューの3つの特徴

　このデータ構造では、データを入れるための「enqueue」メソッドと、データを取り出すための「dequeue」メソッドを持ちます。データを出し入れするメソッドの名前は、ほかのものが付けられていることもあります。例えば、「insert」「remove」が使われることもありますし、「add」「delete」が使われることもあります。

　「queue」ばかりになってしまいますが、本稿では「enqueue」「dequeue」を使うことにします。

　またキューでは、複数のデータを保持できます。複数のデータを保持できるデータ構造としては「配列」などがあります。配列は、添え字を指定することで、値を保持する場所やどこから値を取り出すかを指定できましたが、キューでは、そういったことはできません。データを入れた順にしかデータを取り出すことができないから必要がないのです。

　使い勝手を良くするために、「キューに値が入っているのか」「キューに値を入れることができるか」を確認できるようなメソッドを持たせることもあります。

キューの動作

　次の図では、キューの動作を具体的に示しています。

図　キュー構造の動き

　1を挿入すると、キューには1が入ります。2、3と順に挿入すると、その順にデータはキューに入ります。“取り出し”をすると、先頭の1が取り出せます。その後に4を挿入すると、最後に4が追加されます。次に取り出しを2回続けると、2、3が取り出せます。これは、挿入した順になっています。

【お題】キュー構造をJava言語で実装できますか？

　それでは、「最大5つまで、0以上のint型の値を保持できる、キューを使ったプログラム」について考えてみましょう。

　クラス「Queue」はキュー構造を表しています。フィールドとしては、キューにどれだけの要素数を保存できるかを表す定数「SIZE」、値を入れるための配列「values」、先頭にあるデータの位置を表す変数「head」、末尾にあるデータの位置を表す変数「tail」を用意します。

　メソッドとしては「enqueue」「dequeue」を用意します。キューが空かどうかを調べる「isEmpty」メソッドも用意します。

データを入れるenqueueメソッド

　データを入れる際には、用意してあるvaluesへ順番に入れていけばいいので、単純に考えると、次のようなコードになります。

    boolean enqueue(int data) {
        if (data < 0) return false;
        if (tail > SIZE) {
            return false;
        }
        values[tail++] = data;
        tail = tail % values.length;
        return true;
    }

　dataは0以上の値なので、それをチェックします。次に、末尾を指しているtailを使って、「配列へ、これ以上データを入れられるかどうか」を判定します。入れられないならfalse、入れられるならtrueを返すようにします。データを入れられる場合は、「values[tail]」へ値を入れて、tailを1増分します。1行で表すために「values[tail++] = data;」とします。

データを取り出すdequeueメソッド

　データを取り出すメソッドについて考えてみましょう。先ほどのenqueueメソッドと対応して考えるなら、次のようなコードになります。

    int dequeue() {
        int data = -1;
        if (tail != head) {
            data = values[head++];
        }
        return data;
    }

　キューにデータがない場合は、headとtailの位置が一致しているので、その場合は「-1」を返します。そうでない場合は、headが先頭を指しているわけですから、values[head]から値を取り出し、headを1増分します。そして、取り出した値を返します。このようにすることで、利用する側では「-1」が返って来たら、キューにデータがないと判定できます。

キューが空かどうかを返すisEmptyメソッド

　キューが空かどうかを返すisEmptyメソッドはキューにデータがない場合は、headとtailの位置が一致しますから、次のようになります。

    boolean isEmpty() {
        return (tail == head);
    }

配列の先頭のデータ領域を再利用する配列の先頭のデータ領域を再利用する

　以上が基本ですが、このままでは配列の最後の要素にデータを入れたら、それ以上使えなくなってしまいます。ここで、配列の先頭の要素にあるデータが取り出されている場合は、その領域は再利用できます。ですから、そこを上手に利用することを考えてみましょう。

　すると、次のようなコードになります。ここでは、Queueクラスを利用するサンプルもmainメソッドとして実装しています。

package sample19;
 
public class Sample01 {
    static class Queue {
        final int SIZE = 5;
        private int[] values = new int[SIZE+1];
        private int head = 0;
        private int tail = 0;
        boolean enqueue(int data) {
            if (data < 0) return false;
            if (((tail + 1) % values.length) == head) {
                return false;
            }
            values[tail++] = data;
            tail = tail % values.length;
            return true;
        }
        int dequeue() {
            int data = -1;
            if (tail != head) {
                data = values[head++];
                head = head % values.length;
            }
            return data;
        }
        boolean isEmpty() {
            return (tail == head);
        }
    }
 
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        q.enqueue(6); // 容量オーバー
        System.out.println(q.dequeue()); // 1
        q.enqueue(7); // 空きがあるのでデータ保持
        while (!q.isEmpty()) {
            int data = q.dequeue();
            System.out.print(data+",");
        }
        // ↑ 2,3,4,5,7, 出力
        System.out.println("");
    }
}

　このプログラムでは、剰余を計算するための演算子「%」をうまく利用しています。headやtailが配列の要素数を超える値となる場合は、0に戻るように計算をしています。配列が空なのか判定する処理は変えていませんが、最大容量に達しているかどうかを判定するための処理は「((tail + 1) % values.length) != head」としています。

　キューが空の場合と最大容量に達している場合との区別ができるように、配列の要素数は、キューで保存できる値の最大値よりも1大きくしてあります。同じ値にしてしまうと、これらの区別が付かなくなります。

キューの動作を確認するmainメソッド

　このキューの動作を確認するために、mainメソッドでは、「1」から「7」まで順番にデータをキューへ入れています。ただし、途中の「6」を入れたときに容量オーバーとなるので、一度だけキューからデータを取り出しています。このとき先頭の「1」が取り出されます。それから、「7」を入れています。最後に、キューが空になるまでデータを取り出しています。

実行結果

　実際の実行結果は次のとおりです。想定どおり6は入りません。ほかの値は挿入した順番どおりに取り出せています。

1
2,3,4,5,7,

キューでさまざまなデータ型を使うために

　さて、キューについての説明は以上ですが、このデータ構造について理解できたでしょうか。キューの利便性についてはあまり分からなかったかもしれませんが、ここでは、「こういったデータ構造がよく使われる場面がある」ということだけ覚えておけばいいでしょう。

　次ページからは、キュー構造のコードを3段階で改訂して、ジェネリックスをじっくりと、しかし確実に理解していきます。