<<PREV | ToC | NEXT>>

インタフェースQueueの実装クラス

Revised: May/10th/2008; Since: Aug./07th/2005

Queueインタフェース

インタフェースjava.util.Queue（API仕様）は、J2SE 5.0で追加されました。インタフェースCollectionを直接継承し、Set, Listと並んで、コレクション・フレームワークの基底となるインタフェースです。

実装クラスが表すキューは、FIFO （先入れ先出しの待ち行列）か LIFO （後入れ先出しのスタック）を表すことが多いでしょう。概念的には、特殊なListに似ています。

Collectionに追加して宣言するメソッドは次のメソッドです。挿入／削除／検査に対して、2つづつメソッドが用意されています。

挿入時に対して空きがない場合、add()はIllegalStateExceptionがスローされ、offer()はfalseを返します。削除と検査の場合に要素が存在しない場合は、remove()とelement()はNoSuchElementExceptionがスローされ、poll()とpeek()はnullを返します。

BlockingQueueインタフェース

待ち行列のブロッキングについては、Queueのサブインタフェースjava.util.concurrent.BlockingQueue（API仕様）でサポートされています。

要素の追加と削除に対して、put()とtake()では、処理可能になるまで（空き領域が生じるか、処理対象の要素が追加されるまで）待機します。一方、offer()とpoll()では、タイムアウト値を指定します。待機時間がタイムアウト値を超えると、offerの場合はfalseを、poll()の場合はnullを返します。

例えば、実装クラスの一つjava.util.concurrent.ArrayBlockingQueueの場合、固定長のFIFOキュー（先入れ先出し待ち行列）が生成され、put()するときにキューが埋まっている場合は、空きが生じるまで待たされます。take()するときにキューが空の場合も、要素が追加されるまで待たされます。

Dequeインタフェース

Java SE 6では、Queueのサブインタフェースとして、インタフェースDeque（API仕様）が追加されました。

Queueに対して、両端での追加／削除をサポートするように拡張されています。Dequeは、"Double Ended Queue"の省略で、「デック」と発音するそうです（キューから要素を取り出す「デキュー」ではありません）。

両端を操作するメソッドは次の通りです。

Queueインタフェースで定義されているメソッドはFIFO（先入れ先出し）キューを実装するために、最後尾に追加し、先頭から取り出すように動作します。一方、LIFO（後入れ先出し）キューはStackで実装されており、そちらでは先頭に追加し、先頭から取り出します。

上記のDequeメソッドの中で、Queueメソッドと対応するのは次の通りです。LinkedListは両方のインタフェースを実装しているので、全てのメソッドが使えます。

同様に、Stackメソッドと対応するのは次の通りです。Stackメソッドはコレクション・フレームワークよりも古いクラスであり、要素数が条件を満たしていない場合は、例外をスローするメソッドと、特殊な値を返すメソッドが混じっています。

Queueの利用

基本的なメソッド

次の例では、Queueのメソッドoffer()（要素を最後尾に追加）, peek()（先頭の要素の取り出し）, poll()（先頭の要素の参照）を使っています。

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayDeque;
import java.util.concurrent.ArrayBlockingQueue;

class TestQueue {
	public static void main(String[] args) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue = setQueue(queue);
		consumeQueue(queue);

		Queue<Integer> queue2 = new ArrayBlockingQueue<Integer>(3);
		queue = setQueue(queue2);
		consumeQueue(queue2);

		Queue<Integer> queue3 = new ArrayDeque<Integer>();
		queue = setQueue(queue3);
		consumeQueue(queue3);
	}

	static Queue<Integer> setQueue(Queue<Integer> queue) {
		System.out.println("---- " + queue.getClass().getName() + " ----");
		for ( int i = 0;i < 6;i++ ) {
			System.out.println("offer(): " + queue.offer(i) + ": " + queue);
		}
		return queue;
	}
	
	static <E> void consumeQueue(Queue<E> queue) {
		for (int i = 0; i < 9; i++) {
			System.out.println("peek(): " + queue.peek() + ": " + queue);
			System.out.println("poll(): " + queue.poll());
		}
	}

}

次の実行結果を見ると、offer()は最後尾に要素を追加し、poll()は先頭から要素を削除していることが分かります。先に入れたものが先に取り出されているので、FIFOキューを実装していることになります。

また、空のキューに対するpoll()とpeek()はnullを返すことが分かります。remove()とelement()に変更すると、例外がスローされます。キューのサイズを指定しているArrayBlockingQueueでは、サイズを超えたoffer()がfalseを返しています。add()に変更すると、例外がスローされます。

C:\java>javac TestQueue.java

C:\java>java TestQueue
---- java.util.LinkedList ----
offer(): true: [0]
offer(): true: [0, 1]
offer(): true: [0, 1, 2]
offer(): true: [0, 1, 2, 3]
offer(): true: [0, 1, 2, 3, 4]
offer(): true: [0, 1, 2, 3, 4, 5]
peek(): 0: [0, 1, 2, 3, 4, 5]
poll(): 0
peek(): 1: [1, 2, 3, 4, 5]
poll(): 1
peek(): 2: [2, 3, 4, 5]
poll(): 2
peek(): 3: [3, 4, 5]
poll(): 3
peek(): 4: [4, 5]
poll(): 4
peek(): 5: [5]
poll(): 5
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null
---- java.util.concurrent.ArrayBlockingQueue ----
offer(): true: [0]
offer(): true: [0, 1]
offer(): true: [0, 1, 2]
offer(): false: [0, 1, 2]
offer(): false: [0, 1, 2]
offer(): false: [0, 1, 2]
peek(): 0: [0, 1, 2]
poll(): 0
peek(): 1: [1, 2]
poll(): 1
peek(): 2: [2]
poll(): 2
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null
---- java.util.ArrayDeque ----
offer(): true: [0]
offer(): true: [0, 1]
offer(): true: [0, 1, 2]
offer(): true: [0, 1, 2, 3]
offer(): true: [0, 1, 2, 3, 4]
offer(): true: [0, 1, 2, 3, 4, 5]
peek(): 0: [0, 1, 2, 3, 4, 5]
poll(): 0
peek(): 1: [1, 2, 3, 4, 5]
poll(): 1
peek(): 2: [2, 3, 4, 5]
poll(): 2
peek(): 3: [3, 4, 5]
poll(): 3
peek(): 4: [4, 5]
poll(): 4
peek(): 5: [5]
poll(): 5
peek(): null: []
poll(): null
peek(): null: []
poll(): null
peek(): null: []
poll(): null

C:\java>

Dequeの例

次の例は、インタフェースDequeの実装クラスの例です。

LIFOキュー（スタック）にするために、先頭に追加して先頭から取得しています（末尾に追加して末尾から取得しても同じです）。

import java.util.Deque;
import java.util.LinkedList;
import java.util.ArrayDeque;
import java.util.concurrent.ArrayBlockingQueue;

class TestDeque {
	public static void main(String[] args) {
		Deque<Integer> queue = new LinkedList<Integer>();
		queue = setQueue(queue);
		consumeQueue(queue);
		
		Deque<Integer> queue2 = new ArrayDeque<Integer>();
		queue = setQueue(queue2);
		consumeQueue(queue2);
	}

	static Deque<Integer> setQueue(Deque<Integer> queue) {
		System.out.println("---- " + queue.getClass().getName() + " ----");
		for ( int i = 0;i < 6;i++ ) {
			System.out.println("offerFirst(): " + queue.offerFirst(i) + ": " + queue);
		}
		return queue;
	}
	
	// 型変数Eを宣言して引数で使っているが、
	// ブロック内で使っていないので意味がない
	static <E> void consumeQueue(Deque<E> queue) {
		for (int i = 0; i < 9; i++) {
			System.out.println("peekFirst(): " + queue.peekFirst() + ": " + queue);
			System.out.println("pollFirst(): " + queue.pollFirst());
		}
        System.out.println();
	}
}

D:\java>javac TestDeque.java

D:\java>java TestDeque
---- java.util.LinkedList ----
offerFirst(): true: [0]
offerFirst(): true: [1, 0]
offerFirst(): true: [2, 1, 0]
offerFirst(): true: [3, 2, 1, 0]
offerFirst(): true: [4, 3, 2, 1, 0]
offerFirst(): true: [5, 4, 3, 2, 1, 0]
peekFirst(): 5: [5, 4, 3, 2, 1, 0]
pollFirst(): 5
peekFirst(): 4: [4, 3, 2, 1, 0]
pollFirst(): 4
peekFirst(): 3: [3, 2, 1, 0]
pollFirst(): 3
peekFirst(): 2: [2, 1, 0]
pollFirst(): 2
peekFirst(): 1: [1, 0]
pollFirst(): 1
peekFirst(): 0: [0]
pollFirst(): 0
peekFirst(): null: []
pollFirst(): null
peekFirst(): null: []
pollFirst(): null
peekFirst(): null: []
pollFirst(): null
---- java.util.ArrayDeque ----
offerFirst(): true: [0]
offerFirst(): true: [1, 0]
offerFirst(): true: [2, 1, 0]
offerFirst(): true: [3, 2, 1, 0]
offerFirst(): true: [4, 3, 2, 1, 0]
offerFirst(): true: [5, 4, 3, 2, 1, 0]
peekFirst(): 5: [5, 4, 3, 2, 1, 0]
pollFirst(): 5
peekFirst(): 4: [4, 3, 2, 1, 0]
pollFirst(): 4
peekFirst(): 3: [3, 2, 1, 0]
pollFirst(): 3
peekFirst(): 2: [2, 1, 0]
pollFirst(): 2
peekFirst(): 1: [1, 0]
pollFirst(): 1
peekFirst(): 0: [0]
pollFirst(): 0
peekFirst(): null: []
pollFirst(): null
peekFirst(): null: []
pollFirst(): null
peekFirst(): null: []
pollFirst(): null

D:\java>

<<PREV | ToC | NEXT>>