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

2007.09.17

先週はキューを説明しました。今週は両端キューであるデックについて説明していきます。

先週紹介したキューは最初に追加した要素を最初に取り出せるFirst In, First Out (FIFO)を特徴とします。

FIFOと同じようによく使われるのがLast In, First Out (LIFO)です。つまり最後に追加した要素が、はじめに取り出せるということです。逆にいえば、最初に追加した要素は、最後にならないと取り出せません。

ところで、みなさんはPEZというお菓子をご存じでしょうか。キャラクタの頭を後ろにのけぞらせるようにすると、1つキャンディが取り出せるというあのお菓子です。

このPEZというかPEZのケース(ディスペンサ)がLIFOなのです。

Pezのディスペンサの中にはバネが入っており、キャンディを追加するとバネが沈んでいきます。そして、最後に追加したキャンディが一番上になります。

キャンディを取り出すときは一番上、つまり一番後に追加したキャンディから取り出します。つまり、LIFOですね。

このLIFOをキューのように実現するにはどうすればいいでしょう。

FIFOであるキューは、要素を末尾から追加して先頭から取り出すというコレクションです。このように考えると、LIFOは末尾から要素を追加し、末尾から取り出せばいいはずです。

これを実現させるために先頭からでも末尾からでも要素の追加や取り出しをできるようにしたキューが両端キュー、つまりデックです。

そして、デックを表すインタフェースとしてjava.util.DequeインタフェースがJava SE 6で導入されたのです。

なお、LIFOに特化させたコレクションとしてスタックがあり、java.util.Stackクラスが提供されています。しかし、StackクラスはVectorクラスなどと同様にJava Collections Framework以前のクラスです。したがって、Stackクラスの使用はなるべく控え、Dequeインタフェースを使うようにしましょう。

Dequeインタフェースには先頭に対する要素の追加、取り出し、検査と、末尾に対する追加、取り出し、検査のメソッドが定義されています。それぞれ、Queueインタフェースと同様に例外をスローの有無により2種類のメソッドがあります。

**表1 Dequeインタフェースのメソッド**
操作	先頭に対する操作		末尾に対する操作
操作	例外をスローする	例外をスローしない	例外をスローする	例外をスローしない
追加	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
取り出し	removeFirst()	pollFirst()	removeLast()	pollLast()
検査	getFirst()	peekFirst()	getLast()	peekLast()

先頭に対する操作はFirstがメソッド名に付加しており、末尾に対する操作はLastが付加しているので、区別は容易です。

DequeインタフェースはQueueインタフェースの派生インタフェースです。このため、offerメソッド、pollメソッド、peekメソッドなどが定義されています。キューに対する要素の追加は末尾に対して行います。したがって、offerメソッドとofferLastメソッドは等価です。

表2にQueueインタフェースのメソッドとDequeインタフェースのメソッドの対応を示しておきます。

**表2 QueueインタフェースとDequeインタフェースの対応**
Queue	Deque
add(e)	addLast(e)
remove()	removeFirst()
element()	getFirst()
offer(e)	offerLast(e)
poll()	pollFirst()
peek()	peekFast()

DequeインタフェースでLIFOを実現させるためには、Firstが付加しているメソッドだけを使用するか、Lastが付加しているメソッドだけを使用します。また、Stackクラスで提供されていたpushメソッド、popメソッドも定義されています。

それでは、先週と同じように基本的な動作をサンプルで確かめていきましょう。

サンプルのソース SimpleDequeSample.java

Dequeインタフェースを実装しているクラスには、配列を利用したArrayDequeクラスやリスト構造を利用したLinkedListクラスなどがあります。ここでは、先週と同様LinkedListクラスを使用しました。

        Deque<String> deque = new LinkedList<String>();
 
        System.out.println("offerLast A: " + deque.offerLast("A"));
        System.out.println("offerLast B: " + deque.offerLast("B"));
        System.out.println("offerLast C: " + deque.offerLast("C"));
 
        showDeque(deque);

DequeインタフェースもQueueインタフェースと同様にジェネリクスで型を指定します。最後の行のshowDequeメソッドはデックをコンソールに出力するために作成したメソッドです。

まず、デックの末尾に要素を追加してみましょう。

offerLast A: true
offerLast B: true
offerLast C: true
A B C

左側が先頭なので、A、B、Cが左側から並びます。

ここで先頭から要素を追加してみます。

        System.out.println("offerFirst D: " + deque.offerFirst("D"));
        System.out.println("offerFirst E: " + deque.offerFirst("E"));
        System.out.println("offerFirst F: " + deque.offerFirst("F"));
 
        showDeque(deque);

先頭に追加したので、Aの前に追加されるはずですが、どうなるでしょう。

offerFirst D: true
offerFirst E: true
offerFirst F: true
F E D A B C

正しくAの前に要素が追加されました。最後に追加したFがデックの先頭になっています。

では、要素を取り出してみましょう。

        System.out.println("pollLast: " + deque.pollLast());
        System.out.println("pollFirst: " + deque.pollFirst());
 
        showDeque(deque);

末尾から要素を取り出したらC、先頭はFになるはずです。

pollLast: C
pollFirst: F
E D A B

予想通りの動作になりました。また、デックはCとFが取りのぞかれて、先頭がE、末尾がBになっています。

次に検査です。

        System.out.println("peekLast: " + deque.peekLast());
        System.out.println("peekFirst: " + deque.peekFirst());
 
        showDeque(deque);

もうどうなるかお分かりですよね。