目次
Queueとは？
定義
通常、キューはFIFO (先入れ先出し)で要素の順序付けを行います。
引用元）https://docs.oracle.com/javase/jp/8/docs/api/java/util/Queue.html
公式に記載がある通り、Queueは先入れ/先出しの構造を提供するインターフェースです。
FIFOとはFirst-in First-outの略です。
構造
筒にどんどん押し込めていくイメージです。
最初に入れたものが出口から押し出される様子をイメージするとわかりやすいです。
add / offer（追加）
remove / poll （取得）
設計上の違い
Queueインターフェースには様々な実装が用意されています。（後述）
それらに共通して提供されている機能があるのですが、用途別に設計が異なります。
| 例外のthrowする | 特殊な値を返す | |
|---|---|---|
| 挿入 | add(e) | offer(e) |
| 削除 | remove() | poll() |
| 検査 | element() | peek() |
例外のthrowする
これらは処理の結果、例外をthrowするメソッドです。
例えばaddの場合、容量制限を超えて追加しようとするとIllegalStateExceptionがthrowされます。
特殊な値を返す
これらは例外をthrowさせることなく、何らかの値を返すメソッドです。
例えばofferの場合、容量制限を超えて追加しようとするとboolean型のfalseが返ります。
Queueインターフェースの実装クラス
Queueインターフェースには様々な実装が用意されており、用途によって使い分けます。
AbstractQueue
特徴
Queueインターフェースを部分的に実装した抽象クラス。- 直接インスタンス化はできず、サブクラスとして他のキュー実装の基礎を提供。
addやofferなどの基本的な操作は実装されているが、キューの内部構造はサブクラスで定義する必要がある。
用途
- 新しいカスタムキュークラスを作成する際の基盤
ArrayBlockingQueue
特徴
- 固定容量のスレッドセーフなキュー。
- 先頭と末尾を効率的に操作するリングバッファを使用。
- ブロッキング操作をサポート（
put,take）。
用途
- プロデューサー-コンシューマー問題の解決。
- キャパシティ制限が必要な場合。
ConcurrentLinkedQueue
特徴
- 非ブロッキングでスレッドセーフなキュー。
- ロックフリーアルゴリズムを使用し、高いスループットを提供。
- 容量制限はない。
用途
- 高スループットが要求される並行処理。
- タスクの共有キュー。
DelayQueue
特徴
- 要素に遅延時間を設定できるスレッドセーフなキュー。
- 遅延時間が経過した要素だけが取得可能。
- 要素は
Delayedインターフェースを実装する必要がある。
用途
- タイマー機能やスケジュールされたタスクの管理。
LinkedBlockingQueue
特徴
- 可変容量または固定容量のスレッドセーフなキュー。
- リンクリストで実装され、キューの操作が効率的。
用途
- 容量制限がある、または効率的なブロッキングキューが必要な場合。
LinkedList
特徴
- 非スレッドセーフなデータ構造。
- リンクリストを基にした可変長のリストで、キューとして利用可能（
QueueやDequeを実装）。
用途
- シンプルなデータ構造が必要な場合。
- スレッドセーフが不要な場合。
LinkedTransferQueue
特徴
- スレッドセーフな無制限キュー。
- 要素の転送（直接のスレッド間受け渡し）をサポート。
- 指定された任意のプロデューサに関して、FIFO (先入れ先出し)で要素を順序付けできる。
用途
- 転送操作を効率化したい場合。
PriorityBlockingQueue
特徴
- 優先順位に基づいて要素を管理するスレッドセーフなキュー。
- 要素の順序付けには
ComparableまたはComparatorを使用。 - 容量は無制限。
用途
- 並行環境での優先順位付きタスクの管理。
- タイマーやジョブスケジューリング。
PriorityQueue
特徴
- 優先順位に基づいて要素を管理する非スレッドセーフなキュー。
- 容量は無制限（自動的にサイズが拡張）。
用途
- シングルスレッド環境での優先順位付きタスクの管理。
SynchronousQueue
特徴
- 容量がゼロのスレッドセーフなキュー。
- 要素は直接的にプロデューサーから消費者に転送される（ストレージなし）。
putはtakeが呼ばれるまでブロックされる。
用途
- 直接的なスレッド間通信。
- 転送中のデータ保持が不要な場合。
用途ごとの比較表
| クラス名 | スレッドセーフ | 容量制限 | 優先順位 | ブロッキング | 用途例 |
|---|---|---|---|---|---|
| AbstractQueue | ❌ | ❌ | ❌ | ❌ | カスタムキューの基盤 |
| ArrayBlockingQueue | ✅ | ✅ | ❌ | ✅ | 容量制限付きのプロデューサー・コンシューマ |
| ConcurrentLinkedQueue | ✅ | ❌ | ❌ | ❌ | 高スループットが要求される並行処理 |
| DelayQueue | ✅ | ❌ | ✅ （遅延時間） | ✅ | タイマーやスケジューリング |
| LinkedBlockingQueue | ✅ | 可変 | ❌ | ❌ | 効率的なブロッキングキュー |
| LinkedList | ❌ | ❌ | ❌ | ❌ | シンプルなキュー操作 |
| LinkedTransferQueue | ✅ | ❌ | ❌ | ✅ | 転送操作の効率化 |
| PriorityBlockingQueue | ✅ | ❌ | ✅ | ✅ | 並行環境での優先順位付きタスク |
| PriorityQueue | ❌ | ❌ | ✅ | ❌ | シングルスレッドでの優先順位管理 |
| SynchronousQueue | ✅ | ✅ （0） | ❌ | ✅ | 転送専用のスレッド間通信 |
使い方の例（LinkedList）
LinkedListでQueueを使う例です。
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.LinkedList; import java.util.Queue; public class LinkedListQueueExample { public static void main(String[] args) { // LinkedListをQueueとして使用 Queue<String> queue = new LinkedList<>(); // add(e) - 要素を追加（成功しなければ例外をスロー） queue.add("A"); queue.add("B"); queue.add("C"); System.out.println("After add operations: " + queue); // offer(e) - 要素を追加（成功すればtrueを返す） boolean offered = queue.offer("D"); System.out.println("Offer result for D: " + offered); // trueが返るはず System.out.println("After offer operation: " + queue); // remove() - 先頭の要素を削除して返す（失敗時は例外をスロー） String removed = queue.remove(); // 先頭の"A"を削除 System.out.println("Removed element: " + removed); // "A"が表示される System.out.println("After remove operation: " + queue); // poll() - 先頭の要素を削除して返す（失敗時はnullを返す） String polled = queue.poll(); // 先頭の"B"を削除 System.out.println("Polled element: " + polled); // "B"が表示される System.out.println("After poll operation: " + queue); // element() - 先頭の要素を返す（失敗時は例外をスロー） String element = queue.element(); // 現在の先頭要素"C"を返す System.out.println("Element at front: " + element); // "C"が表示される // peek() - 先頭の要素を返す（失敗時はnullを返す） String peeked = queue.peek(); // 現在の先頭要素"C"を返す System.out.println("Peek element: " + peeked); // "C"が表示される // 最後の状態 System.out.println("Final queue state: " + queue); } } |
実行結果
After add operations: [A, B, C]
Offer result for D: true
After offer operation: [A, B, C, D]
Removed element: A
After remove operation: [B, C, D]
Polled element: B
After poll operation: [C, D]
Element at front: C
Peek element: C
Final queue state: [C, D]
動作説明
- 追加
add(e): 指定した要素をキューの末尾に追加します。キューが満杯の場合、IllegalStateExceptionがスローされます。offer(e): 要素を末尾に追加しますが、成功した場合はtrueを返します。失敗した場合（例えば、キューが満杯である場合）にはfalseを返します。
- 削除
remove(): キューの先頭から要素を削除して返します。キューが空の場合、NoSuchElementExceptionがスローされます。poll(): 先頭の要素を削除して返しますが、キューが空の場合はnullを返します。
- 検査
element(): 先頭の要素を返しますが、キューが空の場合はNoSuchElementExceptionがスローされます。peek(): 先頭の要素を返しますが、キューが空の場合はnullを返します。
まとめ
- Queueは先入れ先出しの順序で管理するデータ構造を提供する。
- 例外を返すメソッドと特殊な値を返すメソッドの2つの操作性が提供されている。
- 優先度を持つ実装クラスもある。
- 用途によって様々な実装が用意されている。
- ブロッキングキューはリソースが利用可能になるまでスレッドを待機する。
- 容量制限はArrayBlockingQueueで実装できる。
コメント