倭マン's BLOG

くだらない日々の日記書いてます。　たまにプログラミング関連の記事書いてます。　書いてます。

トップ > java.lang/java.util > Java SE 6 コレクション・フレームワークのメソッド (3) : Queue, Deque

Java SE 6 コレクション・フレームワークのメソッド (3) : Queue, Deque

java.lang/java.util Java6

今回は Queue と Deque の2つ（一覧）。

メソッドは独断と偏見で幾つかにカテゴリー分けしてます：

  • 集合としてのメソッド：size() や iterator() など
  • 要素の挿入：add(), offer() など
  • 要素の削除：remove(), poll() など
  • 要素の検査：element(), peek() など

メソッドの役割が分かりにくそうな場合のみ別途説明を。　その他注意点

  • 拡張対象のインターフェースに定義されているメソッドには @Override アノテーションを付与してます。　ただし、インターフェースのメソッドに @Override を付与すると実際にはコンパイルエラーになります。
  • 配列に関するメソッド toArray(..) はここでは無視してます。

Queue インターフェース


Queue は優先順位をつけてオブジェクトを格納するのに使用します。　「キュー」と読みます（書くまでもない？）。

package java.util;
public interface Queue<E> extends Collection<E>{
    // ********** 集合としてのメソッド **********
    @Override int size();
    @Override boolean isEmpty();
    @Override boolean contains(Object o);
    @Override boolean containsAll(Collection<?> c);

    @Override Iterator<E> iterator();

    @Override boolean addAll(Collection<? extends E> c);

    @Override boolean remove(Object o);
    @Override boolean removeAll(Collection<?> c);
    @Override boolean retainAll(Collection<?> c);
    @Override void clear();

    // ********** 要素の挿入 **********
    @Override boolean add(E e) throws IllegalStateException;
    boolean offer(E e);

    // ********** 要素の削除 **********
    E remove() throws IllegalStateException;
    E poll();

    // ********** 要素の検査 **********
    E element() throws IllegalStateException;
    E peek();
}

メソッド

Queue に対して行う処理は、概ねオブジェクトの挿入、削除、検査の3つです。

例外を投げる 失敗時に特定の値を返す
/ 失敗時に返される値
挿入 add(E) offer(E) / false
削除 remove() poll() / null
検査 element() peek() / null

（個人的には）あまりなじみのない英単語「poll」と「peek」の意味は以下のようになってます：

  • poll・・・獲得する、（草木の）枝先を切る、（牛などの）角を切る
  • peek・・・ちらっと見る

メソッドの振る舞いのイメージ図 (?) は下図のようになります：

実装

Queue インターフェースに定義されているメソッドは、概ね FIFO キューを想定していますが、必ずしも実装が FIFO キューである必要はありません。　Queue の JavaDoc には次の3つの実装が書かれています：

♪FIFO キュー♪
first-in-first-out。　最初にキューに入れたオブジェクトが最初にキューから取り出されます。　実装は java.util.LinkedList など。
♪LIFO キュー♪
last-in-first-out。　最後にキューに入れたオブジェクトが最初にキューから取り出されます。　いわゆる「スタック(stack)」。　Queue 型として使用できる FIFO キューの実装はありません。　FIFO キューを使用したい場合は、後で説明する Deque インターフェースとその実装を使用してください。
♪Priority キュー♪
自然順序、もしくは指定された Comparator オブジェクトを使用してキューから取り出す優先順位を決定します。　実装は java.util.PriorityQueue。

Deque インターフェース


Deque はオブジェクトの入出力する位置が2つあるキューです。　「デック」*1と読みます（結構長い間「デキュー」と読んでました）。

package java.util;
public interface Deque<E> extends Queue<E>{
    // ********** 集合としてのメソッド **********
    @Override int size();
    @Override boolean isEmpty();
    @Override boolean contains(Object o);
    @Override boolean containsAll(Collection<?> c);

    @Override Iterator<E> iterator();
    Iterator<E> descendingIterator();

    @Override boolean addAll(Collection<? extends E> c);

    @Override boolean remove(Object o);
    @Override boolean removeAll(Collection<?> c);
    @Override boolean retainAll(Collection<?> c);
    @Override void clear();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);

    // ********** 要素の挿入 **********
    @Override boolean add(E e) throws IllegalStateException;
    void addFirst(E e) throws IllegalStateException;
    void addLast(E e) throws IllegalStateException;

    @Override boolean offer(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);

    void push(E e) throws IllegalStateException;

    // ********** 要素の削除 **********
    @Override E remove() throws IllegalStateException;
    E removeFirst() throws IllegalStateException;
    E removeLast() throws IllegalStateException;

    @Override E poll();
    E pollFirst();
    E pollLast();

    E pop() throws IllegalStateException;

    // ********** 要素の検査 **********
    @Override E element() throws IllegalStateException;
    E getFirst() throws IllegalStateException;
    E getLast() throws IllegalStateException;

    @Override E peek();
    E peekFirst();
    E peekLast();
}

Deque メソッド

Deque にはオブジェクトの出入り口２つ (First, Last) に対してオブジェクトの挿入、削除、検査を行うメソッドが定義されています。　メソッド名は、キューのメソッド offer(), poll(), peek() に対応して、offerFirst(), offerLast(), pollFirst(), pollLast(), ... となっています。　ただし、element() の代わりには getFirst(), getLast() が定義されています*2。

First (Head)
例外を投げる
　		 First (Head)
失敗時に特定の値を返す
/ 失敗時に返される値		 Last (Tail)
例外を投げる
　		 Last (Tail)
失敗時に特定の値を返す
/ 失敗時に返される値
挿入 addFirst(e) offerFirst(e) / false addLast(e) offerLast(e) / false
削除 removeFirst() pollFirst() / null removeLast() pollLast() / null
検査 getFirst() peekFirst() / null getLast() peekLast() / null

Queue メソッド

Deque は Queue を拡張していますが、Deque オブジェクトを Queue オブジェクトとして扱うと FIFO キューとして振る舞います（Last 位置に要素を付け加え、First 位置から要素を取得します）。　したがって、Queue のメソッドに対応する Deque のメソッドは以下のようになります：

Queue のメソッド Deque のメソッド
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

LIFO キューとしてのメソッド

Deque には、LIFO キューとして使用するためのメソッドが3つ定義されています。　それぞれに対応する Deque のメソッドは以下のようになります：

LIFOキューのメソッド Deque のメソッド
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

メソッドの振る舞いのイメージ図は下図：

*1:「deck」と同じ発音だそうです。

*2:Queue に定義するメソッドを element() ではなく get() にすればいいのに・・・と思うのは拙者だけ？