1. Queue インターフェイス: 古典的なキュー（FIFO）
プログラミングでも日常と同じく、単に要素の集合を保持するだけでなく、処理順序を管理することが重要な場面があります。スーパーマーケットの列を想像してください。先頭に近い人が先に対応されます。これは FIFO（先入れ先出し）の原理です。一方、食器棚の皿の山は LIFO（後入れ先出し）の原理で動きます。Java ではこれらの原理に対応するコレクションとして、キューの Queue、両端キューの Deque、スタックの Stack があります。
主な用途:
- 到着順にタスクを処理（タスクキュー、印刷ジョブ、イベント処理）。
- 操作の取り消し（undo/redo）— スタック。
- 式のパース、木やグラフの走査（幅優先/深さ優先）など。
キューとは？
キュー（Queue）は FIFO の原理に基づくコレクションです。要素は末尾に追加され、先頭から取り出されます。店の列と同じで、早く来た人から先に処理されます。
Queue インターフェイスの主要メソッド
| メソッド | 動作 | 戻り値 |
|---|---|---|
|
末尾に要素を追加（例外を投げない） | true/false |
|
末尾に要素を追加（例外を投げる） | true/Exception |
|
先頭要素を削除して返す | 要素/null |
|
先頭要素を削除して返す | 要素/Exception |
|
先頭要素を削除せずに返す | 要素/null |
|
先頭要素を削除せずに返す | 要素/Exception |
似た挙動のメソッドがペアになっています。違いは「やさしさ」です。offer、poll、peek は失敗時に特別な値（通常は null や false）を返し、例外を投げません。一方、add、remove、element は境界状況（空のキュー、場合によっては満杯）で例外を投げます。
例: タスクキュー
import java.util.*;
public class QueueDemo {
public static void main(String[] args) {
Queue<String> tasks = new LinkedList<>();
tasks.offer("歯を磨く");
tasks.offer("体操をする");
tasks.offer("コーヒーを飲む");
while (!tasks.isEmpty()) {
String task = tasks.poll(); // キューの先頭からタスクを取り出す
System.out.println("実行中: " + task);
}
}
}
出力:
実行中: 歯を磨く
実行中: 体操をする
実行中: コーヒーを飲む
なぜ LinkedList がよく使われるのか
インターフェイスは契約であり、実装はいくつかあります。よく使われるのは LinkedList で、両端への追加/削除が高速だからです。ただし優れた代替として ArrayDeque があります。特化型としては PriorityQueue（優先度付きキュー）もあり、これは後述します。
2. Deque インターフェイス: 両端キュー
Deque（Double Ended Queue、デック）は、両端（先頭と末尾）から要素を追加・削除できるキューです。両側にドアがあるバスのように、どちら側からでも乗り降りできます。
Deque = 万能選手: 通常のキュー（FIFO）としても、スタック（LIFO）としても、ハイブリッドとしても使えます。
Deque インターフェイスの主要メソッド
| メソッド | 動作 | 使用例 |
|---|---|---|
|
先頭に追加 | |
|
末尾に追加 | |
|
先頭から削除して返す | |
|
末尾から削除して返す | |
|
先頭を参照（削除しない） | |
|
末尾を参照（削除しない） | |
|
先頭に追加（例外を投げない） | |
|
末尾に追加（例外を投げない） | |
例: Deque をキューとして/スタックとして使う
import java.util.*;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// キュー（FIFO）として使用
deque.offerLast("A");
deque.offerLast("B");
deque.offerLast("C");
System.out.println("キュー (FIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.pollFirst());
}
// スタック（LIFO）として使用
deque.offerLast("1");
deque.offerLast("2");
deque.offerLast("3");
System.out.println("スタック (LIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.pollLast());
}
}
}
出力:
キュー (FIFO):
A
B
C
スタック (LIFO):
3
2
1
なぜ ArrayDeque なのか
ArrayDeque は配列ベースの Deque の高速でコンパクトな実装です。スタックやキュー用途では古い Stack より一般に高速かつ信頼性が高く、固定サイズではありません（メモリによってのみ制限されます）。
3. Stack: スタック — 後入れ先出し（LIFO）
スタックは LIFO の原理に基づくコレクションで、最後に追加した要素を上から取り出します。プログラミングでは、操作履歴（undo）、再帰的な構造（木/グラフ）の走査、式の評価などに役立ちます。
Stack クラス（そしてそれを使うべきでない理由）
Java には Stack クラスがありますが、これは古い Vector を継承しています。現在では新しいプロジェクトでの使用は推奨されません。代わりに Deque/ArrayDeque を使いましょう。
スタック操作（Deque）
| メソッド | 動作 |
|---|---|
|
要素をスタックの頂上に積む |
|
頂上の要素を取り出して返す |
|
頂上の要素を参照 |
注意: Deque ではこれらの操作は addFirst/removeFirst/peekFirst に対応しますが、互換性のために「スタック風」の名前 push/pop/peek も用意されています。
例: ArrayDeque を使ったスタック
import java.util.*;
public class StackDemo {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("一番目");
stack.push("二番目");
stack.push("三番目");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
出力:
三番目
二番目
一番目
なぜ Stack は勧められないのか
- Stack は同期化されており（遅い）、古い Vector を継承しています。
- ArrayDeque はたいてい高速でコンパクトで、スレッドをブロックしません。
- 新しいコードで Stack を見かけたら、通常は ArrayDeque への置き換え候補です。
4. 使い分けの指針
| 構造 | 原理 | 用途 | 代表的な実装 |
|---|---|---|---|
| Queue | FIFO | タスクキュー、イベント処理、印刷、顧客の待ち行列 | |
| Stack | LIFO | Undo/redo、再帰、パーサー、木の走査 | |
| Deque | FIFO/LIFO | バッファ、回文判定、両端キュー、汎用タスク | |
身近な例:
- 銀行の行列 — Queue。
- エディタの操作履歴 — Stack。
- 両側からの乗降があるバスの列 — Deque。
5. コード例: ミニアプリでキューとスタックを実装
例1: 印刷ジョブのキュー
import java.util.*;
public class PrintQueueApp {
public static void main(String[] args) {
Queue<String> printQueue = new ArrayDeque<>();
printQueue.offer("Document1.pdf");
printQueue.offer("Document2.docx");
printQueue.offer("Document3.xls");
while (!printQueue.isEmpty()) {
String doc = printQueue.poll();
System.out.println("印刷中: " + doc);
}
}
}
例2: 操作の取り消しスタック（undo）
import java.util.*;
public class UndoStackApp {
public static void main(String[] args) {
Deque<String> undoStack = new ArrayDeque<>();
undoStack.push("テキストの挿入");
undoStack.push("色の変更");
undoStack.push("画像の削除");
System.out.println("最後の操作: " + undoStack.peek()); // 画像の削除
while (!undoStack.isEmpty()) {
System.out.println("取り消し: " + undoStack.pop());
}
}
}
例3: 両端キュー
import java.util.*;
public class DequeApp {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A");
deque.addLast("B");
deque.addFirst("C");
deque.addLast("D");
System.out.println("先頭から取り出す: " + deque.removeFirst()); // C
System.out.println("末尾から取り出す: " + deque.removeLast()); // D
System.out.println("残り: " + deque); // [A, B]
}
}
6. 実装上の特徴と注意点
- ArrayDeque は、多くの用途で最速かつ汎用的なキュー/スタック実装です。
- LinkedList も Deque を実装しています。役立つ場合もありますが、短いキューでは一般に ArrayDeque より遅いことが多いです。
- PriorityQueue は優先度付きキューで、順序は優先度（自然順序または Comparator）で決まります。通常の FIFO キューではありません。
- Stack は古く、同期化されています。新規プロジェクトでは ArrayDeque を推奨します。
- Deque は先頭と末尾の両方を扱えるため、キューとスタックのシナリオを単一の抽象でカバーできて便利です。
7. キューとスタックでよくあるミス
よくあるミス1: Deque の代わりに Stack を使う。
初心者は名前だけを見て Stack クラスを選びがちです。現代のプロジェクトでは代わりに ArrayDeque（または LinkedList）を用い、push/pop を使います。
よくあるミス2: データ構造の原理に反する使い方。
キューやスタックの要素をインデックスで参照しようとする（例: queue.get(0) や stack.get(0)）。これは NG です — キュー/スタック用のメソッド（peek、poll、pop など）を使いましょう。
よくあるミス3: remove/element/add を無検査で使う。
remove、element、add は、空/満杯の状態で例外を投げることがあります。より安全なのは、特別な値を返す「やさしい」 offer、poll、peek を使うことです。
よくあるミス4: ArrayDeque に null 要素を入れる。
ArrayDeque は null を許可しません。null を追加しようとすると NullPointerException になります。
よくあるミス5: PriorityQueue を通常のキューとして使う。
PriorityQueue では順序が優先度（自然順序または Comparator）で決まります。厳密な FIFO が必要なら、ArrayDeque や LinkedList を使いましょう。
よくあるミス6: for-each で走査中にキュー/スタックを変更する。
for-each 中にコレクションから要素を削除すると、ConcurrentModificationException を引き起こすことがあります。削除にはイテレータを使うか、例のようにループ内で poll/pop を使いましょう。
GO TO FULL VERSION