目次
Dequeとは何か？
Dequeの概念
Dequeとは、両端キュー (double-ended queue) のことです。
データを両端から追加・削除できるのが特徴で、これはQueue と Stack の両方の特徴を持つことを意味します。
addFirst
removeFirst
addLast
removeLast
Dequeを使うメリット
- 柔軟性: QueueとStackの両方の機能を持つため、様々なアルゴリズムやデータ構造の実現に利用できる。
- 効率性: 適切な実装であれば、QueueやStackと比較して、より効率的な処理が可能できる。
- シンプルさ: 複雑なデータ構造を組み合わせる必要がなく、シンプルな実装で済ませられる場合がある。
Deque の使い方
主な使用シーン
- キューとスタックの両方の機能が必要な場合
- 先に入力されたデータを後から処理したい場合と、後に入力されたデータを先に処理したい場合が混在する場合。
- 両端から要素を追加・削除できるため、特定の要素へのアクセスが頻繁な場合。
- 再帰的な処理
- スタックのような機能を活用して、再帰的な処理を効率的に実装する場合。
- 履歴管理
- ブラウザの前ページ、次ページの移動など、履歴管理したい場合。
- 編集履歴を保存し、Undo/Redo操作を行う場合。
- パーサー:
- 構文解析など、入力データを順次処理していく場合（一時的な情報保持に使われる）
Dequeのメソッド
両端ごとにメソッドがあります。
また、操作が完了しなかった際に例外をスローするメソッドと何らかの値（boolean、nullなど）を返すメソッドの2通りが用意されています。
| 操作 | 先頭要素 | 末尾要素 | ||
|---|---|---|---|---|
| 例外をthrow | 特別な値 | 例外をthrow | 特別な値 | |
| 追加 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 削除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
| 確認 | getFirst() | peekFirst() | getLast() | peekLast() |
（※）追加・削除は要素の変更が発生しますが、確認は要素が何かを確認するだけ何も変更しません。
実装例
主に LinkedList と ArrayDeque で実装されます。それぞれ特徴が異なるため、用途に合わせて使い分けることが重要です。
LinkedList
双方向連結リストを基にした実装で、要素の挿入・削除が効率的です。特に、リストの先頭や末尾への要素の追加・削除がO(1)の時間で行えます。
ArrayDeque
配列を基にした実装で、LinkedList に比べてランダムアクセスが高速です。ただし、要素の挿入・削除に伴う配列の再配置が必要になる場合があり、性能が低下する可能性があります。
サンプルコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.util.LinkedList; public class LinkedListDequeExample { public static void main(String[] args) { LinkedList<String> deque = new LinkedList<>(); // ArrayDeque<String> deque = new ArrayDeque<>(); // 要素の追加 deque.addFirst("A"); deque.addLast("B"); deque.addFirst("C"); // 要素の取得 System.out.println(deque.getFirst()); // C System.out.println(deque.getLast()); // B // 要素の削除 deque.removeFirst(); deque.removeLast(); System.out.println(deque); // [A] } } |
LinkedListとArrayDequeの比較
| 特徴 | LinkedList | ArrayDeque |
|---|---|---|
| 基底データ構造 | 双方向連結リスト | 配列 |
| 要素の挿入・削除 | O(1) | O(1)またはO(n) (配列の再配置が必要な場合) |
| ランダムアクセス | O(n) | O(1) |
| メモリ使用量 | 要素数に比例 | 一般的にLinkedListより少ない |
- どちらを選ぶべきか？
- 要素の挿入・削除が頻繁な場合:
LinkedList - ランダムアクセスが必要な場合:
ArrayDeque - メモリ使用量を削減したい場合:
ArrayDeque
- 要素の挿入・削除が頻繁な場合:
ポイント
用途によって性能が変ってくることに注意してください。
Queue・Stackとの違い
Queueとは？
Queueは、先入れ先出し (First In First Out, FIFO) の原則に基づくデータ構造です。
入った順に出ていくことが保証されています。
Stackとは？
Stack は、後入れ先出し (Last In First Out, LIFO) の原則に基づくデータ構造です。
本を積み重ねる様子に例えることができます。
Deque・Queue・Stackの違い
各々の違いをまとめます。
| 特徴 | Deque | Queue | Stack |
|---|---|---|---|
| 要素の追加 | 両端 | 末尾のみ | 片端のみ |
| 要素の削除 | 両端 | 先頭のみ | 片端のみ |
| 用途 | ・先入れ先出し、後入れ先出しの両方 ・より柔軟なデータ構造が必要な場合 | 先入れ先出し | 後入れ先出し |
Deque・Queue・Stackの使い分け
Dequeを使うべきケース
- QueueとStackの両方の機能が必要な場合（例：ブラウザの履歴管理）
- データへのアクセスパターンが動的な場合（例：テキストエディタのUndo/Redo機能）
- より柔軟なデータ構造が必要な場合（例：構文解析）
Queueを使うべきケース
- タスクの処理順序を厳密に守りたい場合（例：印刷ジョブの待ち行列）
- データを一度だけ処理したい場合（例：ネットワークパケットの処理）
Stackを使うべきケース
- 関数呼び出しの履歴管理（例：スタックトレース）
- 中置記法から後置記法への変換（例：中置記法の式を後置記法に変換するアルゴリズム）
- 深さ優先探索（例：グラフ探索のアルゴリズム）
まとめると、各データ構造でしかできない処理で使い分けるのがポイントです。
まとめ
- Dequeとは 両端キュー (double-ended queue) のことで、両端から追加・削除できる構造を持つ。
- QueueとStackの特徴を併せ持っている。
- 主な実装クラスとして、LinkedListとArrayDequeがある。
- 特徴があるので、用途によって使い分けること。
- 要素の挿入・削除が頻繁な場合は
LinkedList - ランダムアクセスが必要な場合やメモリ使用量を削減したい場合:は
ArrayDeque
- Queue・Stackとの使い分けポイントは、各データ構造でしか実現できない場合であること。
コメント