Java SE 6 コレクション・フレームワークのメソッド (4) : LIFO Queue を考える

前回、「Queue インターフェースは FIFO キューだけでなく、LIFO キューとしても使えるけど、実装がない」と書きました。　今回は LIFO キューとして使える Queue の実装を考えてみましょう（一覧）。　クラス名は LIFOQueue とします。

一から作るのは大変ので、実際の処理は LIFO の実装として使われる java.util.LinkedList に任せましょう。　以下、

• private フィールドとコンストラクタ
• java.util.Queue に定義されているメソッド
• java.util.Collection に定義されているメソッド

に分けてみていきましょう。

private フィールドとコンストラクタ

private フィールドとして処理を委譲する Deque オブジェクトを定義し、コンストラクタではそのインスタンス生成を行います。　コンストラクタとしては「引数なし」のものと「コピーコンストラクタ」を定義しておきます。

public class LIFOQueue<E> implements Queue<E> {
    
    private final Deque<E> deque;
    
    /** 引数なしコンストラクタ */
    public LIFOQueue(){
        this(new LinkedList<E>());
    }
    
    /** コピーコンストラクタ */
    public LIFOQueue(Collection<? extends E> c){
        this(new LinkedList<E>(c));
    }
    
    private LIFOQueue(Deque<E> deque){
        this.deque = deque;
    }

    ...
}

Queue に定義されているメソッド

次にQueue に定義されているメソッドを実装します。　Queue に実装されているメソッドとは

• 要素の取得：element(), peek()
• 要素の追加：add(e), offer(e)
• 要素の削除と取得：remove(), poll()

の6つです。

これらの操作を行う基点は、Deque の「First の位置」から行います。

public class LIFOQueue<E> implements Queue<E> {
    
    private final Deque<E> deque;

    ...  // コンストラクタ

    // ********** 要素の取得 **********
    public E element() {
        return this.deque.getFirst();
    }
    
    public E peek() {
        return this.deque.peekFirst();
    }

    // ********** 要素の追加 **********
    public boolean add(E e) {
        this.deque.addFirst(e);
        return true;
    }

    public boolean offer(E e) {
        return this.deque.offerFirst(e);
    }

    // ********** 要素の削除と取得 **********
    public E remove() {
        return this.deque.removeFirst();
    }

    public E poll() {
        return this.deque.pollFirst();
    }
}

注意が必要なのは add() メソッドです。　Queue#add()（というより Collection#add()）メソッドは boolean 値を返す必要がありますが、Deque#addFirst() メソッドは返り値が void となっています（Deque#offerFirst() メソッドは boolean 値を返すので問題なし）。　これはおそらく、当初から LinkedList に定義されていた addFirst() メソッドの返り値を void にしたため、互換性から変更ができなくなってしまったのだと思われます。

この解決方法は簡単で、単に true を返すだけです。　Collection#add() メソッドが「false を返すのは、このメソッドが呼び出された前後で集合の内容が変化していないとき」と定義されているので、Queue, Deque の場合は false を返すことはありません。　（Queue, Deque の内部状態のために）add() 処理に失敗した場合は IllegalStateException を投げなければいけませんが、それは Deque#getFirst() メソッドが行ってくれます。

Collection に定義されているメソッド

これらは単に Deque に定義されているメソッドを呼び出すだけです。

import java.util.*;

/** @author waman */
public class LIFOQueue<E> implements Queue<E> {
    
    private final Deque<E> deque;
    
    ...  // コンストラクタ
    ...  // Quue に定義されているメソッド

    public int size(){
        return this.deque.size();
    }

    public boolean isEmpty(){
        return this.deque.isEmpty();
    }

    ...  // その他
}

まとめ

結果をまとめると以下のようになります（メソッドの順番は少々変えてます）：

import java.util.*;

/** @author waman */
public class LIFOQueue<E> implements Queue<E> {
    
    private final Deque<E> deque;
    
    public LIFOQueue(){
        this(new LinkedList<E>());
    }
    
    public LIFOQueue(Collection<? extends E> c){
        this(new LinkedList<E>(c));
    }
    
    private LIFOQueue(Deque<E> deque){
        this.deque = deque;
    }

    public int size() {
        return this.deque.size();
    }

    public boolean isEmpty() {
        return this.deque.isEmpty();
    }

    public boolean contains(Object o) {
        return this.deque.contains(o);
    }

    public boolean containsAll(Collection<?> c) {
        return this.deque.containsAll(c);
    }

    // ********** 要素の取得 **********
    public Iterator<E> iterator() {
        return this.deque.iterator();
    }
    
    public E element() {
        return this.deque.getFirst();
    }
    
    public E peek() {
        return this.deque.peekFirst();
    }

    // ********** 要素の追加 **********
    public boolean add(E e) {
        this.deque.addFirst(e);
        return true;
    }

    public boolean addAll(Collection<? extends E> c) {
        return this.deque.addAll(c);
    }

    public boolean offer(E e) {
        return this.deque.offerFirst(e);
    }

    // ********** 要素の削除 **********
    public void clear() {
        this.deque.clear();
    }

    public boolean remove(Object o) {
        return this.deque.remove(o);
    }

    public boolean removeAll(Collection<?> c) {
        return this.deque.removeAll(c);
    }

    public boolean retainAll(Collection<?> c) {
        return this.deque.retainAll(c);
    }

    // ********** 要素の削除と取得 **********
    public E remove() {
        return this.deque.removeFirst();
    }

    public E poll() {
        return this.deque.pollFirst();
    }

    // ********** 配列 **********
    public Object[] toArray() {
        return this.deque.toArray();
    }

    public <T> T[] toArray(T[] a) {
        return this.deque.toArray(a);
    }
}