「Java SE 6完全攻略」第43回両端キュー：デックその1

2007.09.10

今週から、java.utilパッケージの新機能を紹介していきます。

java.utilパッケージの新機能の中ではじめに紹介するのが、Dequeインタフェースです。

DequeはDouble Ended Queueの略で、日本語で表すとすれば両端キューになります。また、Dequeは、デキューではなく、デックと読みます。

デックはその名のとおりキューを拡張したものです。そこで、まずキューの解説をしてから、デックの解説をしていきます。

キュー

キューは、リストやセットなどのオブジェクトを格納するためのコレクションの一種です。

リストは順番あり重複ありのコレクション、セットは順序なし重複なしのコレクションです。ではキューはどのようなコレクションなのでしょうか。

キューはいうなれば待ち行列です。

行列のできるレストランってありますよね。ラーメン屋でもケーキ屋でもいいのですが、人気がある店は行列ができます^注1。

行列は早く並んだ人が早く店の中に入れます。しかし、横から割り込みをすれば文句を言われます。

このようにはじめに並んだものがはじめに列から抜けでられることをFirst In, First Out、略してFIFOといいます。

そして、FIFOを実現するコレクションがキューというわけです。

たとえば、キューにAを追加し、次にBを追加、最後にCを追加したとします。これを表したのが図1です。この状態で要素を取り出すと図2のように最初に追加したAが取り出せます。

図1 キューに追加


図2 キューから取り出し

キューはイベントキューなど、様々な箇所で使用されています。それなのに、J2SE 5.0まではQueueインタフェースが提供されていなかったのです。Listインタフェースを使えば、キュー相当のクラスは簡単に作れるからかもしれません。

キューの基本操作は、要素の追加、取り出し、そして検査です。

最後の検査というのはキューから取り出さないまま、要素を取得する動作です。たとえば、図2の状態で検査を行なうとBを得ることができますが、キューにはBとCが残ったままになります。

このような操作を持つコレクションとしてjava.util.Queueインタフェースが使われます。

Queueインタフェースは追加、取り出し、検査の3種類の操作に対し、2つずつ、合計6種類のメソッドが定義されています(表1)。

2つずつというのはそれぞれの操作に対して、チェックすべき例外をスローするメソッドと、しないメソッドがあるためです。

**表1 Queueインタフェースのメソッド**
操作	例外をスローする	例外をスローしない
追加	add(e)	offer(e)
取り出し	remove()	poll()
検査	element()	peek()

たとえば、キューのサイズが決まっており、要素が追加する余地がない場合、addメソッドをコールするとIllegalStateException例外がスローされます。一方のofferメソッドは追加できないと戻り値がfalseになるだけです。

また、キューに要素がない場合、removeメソッドやelementメソッドはNoSuchElementException例外がスローされます。もう一方のpollメソッドとpeekメソッドは戻り値がnullになります。

どちらのメソッドを使うかは、キューに対する操作が失敗したときそれを例外として扱うかどうかというポリシーで決めます。

QueueインタフェースはCollectionインタフェースの派生インタフェースです。したがって、ここで示した6種類のメソッド以外に、Collectionインタフェースで定義されたメソッドも使用することができます。

では実際にサンプルで試してみましょう。

サンプルのソース SimpleQueueSample.java

Queueインタフェースを実装しているクラスにはLinkedListクラスやPriorityQueueクラスなどがあります。ここではLinkedListクラスを使いました。

        Queue<String> queue = new LinkedList<String>();
 
        System.out.println("offer A: " + queue.offer("A"));
        System.out.println("offer B: " + queue.offer("B"));
        System.out.println("offer C: " + queue.offer("C"));
        System.out.println("offer D: " + queue.offer("D"));
 
        showQueue(queue);

Queueインタフェースも他のコレクションインタフェースと同様に要素の型をジェネリクスで指定する必要があります。

最後のshowQueueメソッドはコンソールにキューの状態を表示するメソッドです。

これを実行してみると、次のようになります。

offer A: true
offer B: true
offer C: true
offer D: true
A B C D

最後の行がshowQueueメソッドで出力された結果です。左端がキューの先頭で、Aが先頭にあることが分かります。キューの末尾はDになっており、追加した順序で並んでいます。

この状態でまた要素を追加してみましょう。

        System.out.println("offer E: " + queue.offer("E"));
        System.out.println("offer F: " + queue.offer("F"));
        System.out.println("offer G: " + queue.offer("G"));
 
        showQueue(queue);

キューにE、F、そしてGを追加しています。実行結果は、次のようになります。

offer E: true
offer F: true
offer G: true
A B C D E F G

先ほどの末尾だったDの後にE、F、Gが追加されます。

さて、ここで要素を取り出してみます。

        System.out.println("poll: " + queue.poll());
        System.out.println("poll: " + queue.poll());
 
        showQueue(queue);

pollメソッドは引数なしで、取り出した要素が戻り値になります。

poll: A
poll: B
C D E F G

1回目のpollメソッドをコールすることで、キューの先頭のAが取り出せます。この状態では、キューの先頭はAがなくなるので、Bが先頭となります。そして、2回目のpollメソッドのコールでBが取得できます。

AとBを取り出したので、キューの先頭はCになります。

最後がキューに対する検査です。

        System.out.println("peek: " + queue.peek());
 
        showQueue(queue);

検査を行なうのはpeekメソッドです。pollメソッドと同様に、取り出した要素が戻り値になります。

peek: C
C D E F G

pollメソッドと異なり、peekメソッドをコールしてもキューから要素が取り出されていないことが分かります。

最後にshowQueueメソッドを紹介しておきましょう。

    private <E> void showQueue(Queue<E> queue) {
        for (E e: queue) {
            System.out.print(e + " ");
        }
        System.out.println();
    }

QueueインタフェースがCollectionインタフェースの派生インタフェースだということは上述しましたが、Iterableインタフェースの派生インタフェースでもあります。

このため、拡張for文を使用することが可能です。showQueueメソッドも拡張for文を使用して要素を標準出力に出力しているだけです。

今週はキューの基本的な操作を紹介しました。ここでは紹介しませんでしたが、優先度を持ったPriorityQueueクラスも提供されています。

長くなってしまったので、本題のデックは来週紹介することにしましょう。

お楽しみに。

注1 予約をしなくてはいけないレストランは考えないことにします。

著者紹介櫻庭祐一

横河電機ネットワーク開発センタ所属。Java in the Box 主筆