Deque（ArrayDeque） — 両端操作、高速スタック/キュー
Java の Deque（Double Ended Queue）は「両端から追加・削除できる」データ構造です。代表的な実装が ArrayDeque。
初心者が理解すべきポイントは「スタック（後入れ先出し）」「キュー（先入れ先出し）」を両方効率的に扱えることです。
特徴
- 両端操作: 先頭・末尾どちらからも追加・削除可能。
- 高速:
ArrayDequeは配列ベースで、LinkedListより高速なことが多い。 - 用途:
- スタック（push/pop）
- キュー（offer/poll）
- 両端キュー（双方向処理）
👉 null 要素は入れられない点に注意。
基本コード例
1. キューとして利用（FIFO: 先入れ先出し）
import java.util.ArrayDeque;
import java.util.Deque;
public class QueueDemo {
public static void main(String[] args) {
Deque<String> queue = new ArrayDeque<>();
queue.offer("Task1");
queue.offer("Task2");
queue.offer("Task3");
System.out.println(queue.poll()); // Task1
System.out.println(queue.poll()); // Task2
System.out.println(queue.poll()); // Task3
}
}
2. スタックとして利用（LIFO: 後入れ先出し）
Deque<String> stack = new ArrayDeque<>();
stack.push("Item1");
stack.push("Item2");
stack.push("Item3");
System.out.println(stack.pop()); // Item3
System.out.println(stack.pop()); // Item2
System.out.println(stack.pop()); // Item1
3. 両端操作
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // 先頭に追加
deque.addLast("B"); // 末尾に追加
deque.addFirst("C"); // 先頭に追加
System.out.println(deque); // [C, A, B]
System.out.println(deque.removeLast()); // B
System.out.println(deque.removeFirst()); // C
性能の考え方
| 操作 | 計算量 | 特徴 |
|---|---|---|
| addFirst / addLast | O(1) | 両端追加が高速 |
| removeFirst / removeLast | O(1) | 両端削除が高速 |
| push / pop | O(1) | スタック操作 |
| peek / poll | O(1) | キュー操作 |
👉 ランダムアクセスはできない（インデックス指定不可）。順序操作に特化。
例題で練習
例題1: ブラウザの戻る/進む機能
Deque<String> history = new ArrayDeque<>();
history.push("Page1");
history.push("Page2");
history.push("Page3");
System.out.println("戻る: " + history.pop()); // Page3
System.out.println("戻る: " + history.pop()); // Page2
例題2: タスク処理（キュー）
Deque<String> tasks = new ArrayDeque<>();
tasks.offer("Email");
tasks.offer("Report");
tasks.offer("Meeting");
while (!tasks.isEmpty()) {
System.out.println("処理: " + tasks.poll());
}
例題3: 両端からの処理
Deque<String> dq = new ArrayDeque<>();
dq.addLast("Right1");
dq.addFirst("Left1");
dq.addLast("Right2");
System.out.println(dq); // [Left1, Right1, Right2]
// 両端から取り出す
System.out.println(dq.removeFirst()); // Left1
System.out.println(dq.removeLast()); // Right2
テンプレート集
宣言
Deque<Type> deque = new ArrayDeque<>();
キュー操作
deque.offer(value); // 末尾追加
deque.poll(); // 先頭削除
deque.peek(); // 先頭参照
スタック操作
deque.push(value); // 先頭追加
deque.pop(); // 先頭削除
両端操作
deque.addFirst(value);
deque.addLast(value);
deque.removeFirst();
deque.removeLast();
実務でのコツ
- スタック用途:
StackクラスよりArrayDequeを使うのが推奨。 - キュー用途:
LinkedListより軽量で高速。 - 両端処理: アルゴリズム（幅優先探索、双方向処理）で便利。
- スレッド安全:
ArrayDequeは非同期。並行環境ではConcurrentLinkedDequeを検討。
まとめ
- Deque は両端操作可能なデータ構造。
- ArrayDeque は高速で、スタック・キュー両方に使える。
- ランダムアクセスはできないが、順序操作に特化している。
👉 練習課題として「ArrayDeque を使って、先頭から処理する通常キューと末尾から処理する逆順キューを同時に実装」してみると、Deque の柔軟さが体感できます。