今回は 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 にはオブジェクトの出入り口2つ (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() |
メソッドの振る舞いのイメージ図は下図: