［Java 5］LinkedListでFIFOを表現しキューを実現：JavaTips 〜Javaプログラミング編

[平野正喜，＠IT]

8つのQueueクラスの使い分け

　オブジェクトの後入れ先出し（LIFO）スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し（FIFO）を表す待ち行列（キュー）は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

　Queueインターフェイスは「処理の前に要素を保持する目的で設計されたコレクション」と定義されています。また、通常、キューはFIFOで要素の順序付けを行いますが、指定されたコンパレータ（比較関数）に従って要素の順序付けを行う「優先度キュー」も導入されました。

　実際にキューを利用するには、Queueインターフェイスと、サブインターフェイスであるBlockingQueueを実装する8つのクラスを使い分けることになります。BlockingQueueはブロックキューを実現するインターフェイスで、ブロックキューは、要素の取得時にキューが空でなくなるまで待機したり、要素の格納時にキュー内の空間が利用可能になるまで待機する操作もサポートする拡張型のキューです。

	クラス名	特徴
	AbstractQueue	キューへの追加と削除用の5つの基本メソッドを持つ抽象クラス
	ArrayBlockingQueue	標準的なバウンドバッファ（配列に基づくFIFOのバウンド形式のブロックキュー）を提供するクラスで、均等性ポリシーをサポートする
	ConcurrentLinkedQueue	共通のキューへのアクセスを多数のスレッドが共有する場合に用いる、アンバウンド形式のスレッドセーフなキューを提供するクラス
	DelayQueue	遅延時間の経過後にのみ、要素を取得できるDelayed要素のアンバウンド形式のブロックキューを提供するクラス
	LinkedBlockingQueue	リンクノードに基づくFIFOのバウンド形式のブロックキューを提供するクラスで、配列ベースのキューよりもスループットが大きい
	LinkedList	Java 1.2からあるリンクリストの実装クラス。Java 5からキューまたは双方向キューとして使用できるようになった
	PriorityQueue	優先度キューを提供するクラス。優先度キューは指定されたコンパレータまたは自然順序付けによる優先度を指定できる
	PriorityBlockingQueue	アンバウンド形式のBlockingQueueである優先度キューを提供するクラス
	SynchronousQueue	同期キューを提供するクラス。同期キューは要素のキューへの追加が先頭の取得＆削除を待機するブロックキュー

Genericsを用いたスタックとキューのサンプルプログラム

　8つのクラスのうち7つは今回新たに追加されたクラスですが、LinkedListだけが以前から存在したクラスへの仕様追加になっています。そこで、一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

　なお、このプログラムでは、Java 5から登場したGenericsを用いて、キューとスタックの要素を文字列（String）に設定しています。

図1　キューとスタックを試すプログラム

　キューがスタックに近い形で利用可能になっているのが、実感できます。

Profile

RunDog.org

平野正喜