Queue と Deque インターフェース - Java コレクションフレームワーク

Queue インターフェースの概要

Queue<E> インターフェースは、キューを定義します。キューは、要素を一方の端（末尾）から追加し、もう一方の端（先頭）から取り出す FIFO（First-In-First-Out：先入れ先出し）の原則に従うコレクションです。

Queue の主な特徴

FIFO 原則: 最初に追加された要素が最初に取り出される
末尾への追加: 要素は常にキューの末尾に追加される
先頭からの取り出し: 要素は常にキューの先頭から取り出される
容量制限: 実装によっては容量制限がある場合がある

Deque インターフェースの概要

Deque<E> インターフェースは、両端キュー（Double-Ended Queue）を定義します。両端キューは、先頭と末尾の両方から要素の挿入と削除が可能なコレクションです。Dequeは「デック」と発音され、スタックとキューの両方の機能を組み合わせたものと考えることができます。

Deque の主な特徴

両端操作: 先頭と末尾の両方から要素の追加・削除が可能
スタックとして使用可能: LIFO（後入れ先出し）操作をサポート
キューとして使用可能: FIFO（先入れ先出し）操作をサポート
Null許容: 実装によってはnull要素を格納できます

主な Queue と Deque 実装クラス

ArrayDeque

ArrayDeque は可変サイズの配列に基づく Deque インターフェースの実装です。内部的には循環配列を使用して効率的な両端操作を実現しています。

ArrayDeque の特徴

両端の操作が高速: 先頭・末尾への追加・削除は O(1) の時間計算量
null要素を許容しない: null を挿入しようとすると NullPointerException が発生
容量の自動拡張: 要素数が増えると自動的に容量が拡張される
非同期: スレッドセーフではないため、複数スレッドでの使用には外部同期が必要
LinkedList より効率的: 一般的にメモリ使用量が少なく、キャッシュの局所性が高い

ArrayDeque の基本的な使用例

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // ArrayDeque の作成
        Deque<String> deque = new ArrayDeque<>();
        
        // 末尾への追加
        deque.addLast("りんご");
        deque.addLast("バナナ");  // [りんご, バナナ]
        
        // 先頭への追加
        deque.addFirst("オレンジ");  // [オレンジ, りんご, バナナ]
        
        // 先頭要素の取得（削除なし）
        String first = deque.peekFirst();  // "オレンジ"
        
        // 末尾要素の取得（削除なし）
        String last = deque.peekLast();  // "バナナ"
        
        // 先頭要素の取得と削除
        String removed = deque.pollFirst();  // "オレンジ"を取得して削除 -> [りんご, バナナ]
        
        // スタックとして使用（LIFO）
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);  // 先頭に追加
        stack.push(2);
        stack.push(3);  // [3, 2, 1]
        
        int top = stack.pop();  // 3を取得して削除 -> [2, 1]
        
        // キューとして使用（FIFO）
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(1);  // 末尾に追加
        queue.offer(2);
        queue.offer(3);  // [1, 2, 3]
        
        int head = queue.poll();  // 1を取得して削除 -> [2, 3]
    }
}

LinkedList

LinkedList は双方向リンクリストに基づく実装で、List インターフェースと Deque インターフェースの両方を実装しています。

LinkedList の特徴（Deque として）

両端の操作が高速: 先頭・末尾への追加・削除は O(1) の時間計算量
null要素を許容する: null を挿入可能
メモリ使用量が多い: 各要素がノードとして実装され、前後の参照を保持するため
非同期: スレッドセーフではない
List としても使用可能: インデックスベースのアクセスも提供

LinkedList を Deque として使用する例

import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        // LinkedList を Deque として使用
        Deque<String> deque = new LinkedList<>();
        
        // 要素の追加
        deque.offerFirst("最初");
        deque.offerLast("最後");
        deque.addFirst("新しい最初");
        deque.addLast("新しい最後");  // [新しい最初, 最初, 最後, 新しい最後]
        
        // 要素の参照（削除なし）
        String first = deque.peekFirst();  // "新しい最初"
        String last = deque.peekLast();    // "新しい最後"
        
        // 要素の取得と削除
        String removedFirst = deque.pollFirst();  // "新しい最初"を削除
        String removedLast = deque.pollLast();    // "新しい最後"を削除
        
        // イテレーション
        for (String item : deque) {
            System.out.println(item);  // 最初, 最後
        }
    }
}

ArrayDeque と LinkedList の比較

特性	ArrayDeque	LinkedList
両端操作（追加/削除）	O(1) - 高速	O(1) - 高速
メモリ使用量	少ない	多い
null要素	許容しない	許容する
インデックスアクセス	サポートなし	サポートあり（ただしO(n)）
イテレーション性能	高い（キャッシュフレンドリー）	低い（メモリの局所性が低い）

選択のガイドライン

ArrayDequeを選ぶ場合:
- 純粋なスタックやキューとして使用する
- メモリ効率が重要
- null要素を格納する必要がない
- 高速なイテレーションが必要
LinkedListを選ぶ場合:
- Dequeとリスト操作の両方が必要
- null要素を格納する必要がある
- インデックスベースのアクセスも必要

Deque の主な操作メソッド

操作	先頭（First/Head）	末尾（Last/Tail）	例外発生
挿入	addFirst(e)	addLast(e)	容量制限時に例外
挿入	offerFirst(e)	offerLast(e)	失敗時にfalseを返す
削除と取得	removeFirst()	removeLast()	空の場合に例外
削除と取得	pollFirst()	pollLast()	空の場合にnullを返す
参照（削除なし）	getFirst()	getLast()	空の場合に例外
参照（削除なし）	peekFirst()	peekLast()	空の場合にnullを返す

スタックとキューの操作

スタック操作	キュー操作	Deque同等操作
push(e)	-	addFirst(e)
pop()	-	removeFirst()
peek()	-	peekFirst()
-	add(e)	addLast(e)
-	offer(e)	offerLast(e)
-	remove()	removeFirst()
-	poll()	pollFirst()
-	element()	getFirst()
-	peek()	peekFirst()

Deque の活用例

1. スタックとしての使用

Java SE 6以降、Stack クラスの代わりに ArrayDeque を使用することが推奨されています。

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStackExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        
        // スタックに要素を追加（push）
        stack.push("最初の要素");
        stack.push("2番目の要素");
        stack.push("最後の要素");  // [最後の要素, 2番目の要素, 最初の要素]
        
        // スタックの先頭を確認（削除なし）
        String top = stack.peek();  // "最後の要素"
        
        // スタックから要素を取り出す（pop）
        String popped = stack.pop();  // "最後の要素"
        popped = stack.pop();         // "2番目の要素"
        
        // スタックが空かどうか確認
        boolean isEmpty = stack.isEmpty();  // false
    }
}

2. キューとしての使用

FIFO（先入れ先出し）キューとして使用する場合も ArrayDeque が効率的です。

import java.util.ArrayDeque;
import java.util.Queue;

public class DequeAsQueueExample {
    public static void main(String[] args) {
        // Queueインターフェースとして使用
        Queue<String> queue = new ArrayDeque<>();
        
        // キューに要素を追加
        queue.offer("1番目");
        queue.offer("2番目");
        queue.offer("3番目");  // [1番目, 2番目, 3番目]
        
        // キューの先頭を確認（削除なし）
        String head = queue.peek();  // "1番目"
        
        // キューから要素を取り出す
        String removed = queue.poll();  // "1番目"
        removed = queue.poll();         // "2番目"
        
        // 要素数の確認
        int size = queue.size();  // 1
    }
}

3. スライディングウィンドウの実装

Deque は、最近の N 個の要素を保持するスライディングウィンドウの実装に適しています。

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowExample {
    public static void main(String[] args) {
        // 最大3要素のスライディングウィンドウ
        Deque<Integer> window = new ArrayDeque<>(3);
        int windowSize = 3;
        
        // データストリームをシミュレート
        int[] stream = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        for (int value : stream) {
            // ウィンドウが最大サイズに達したら、最も古い要素を削除
            if (window.size() == windowSize) {
                window.pollFirst();
            }
            
            // 新しい要素をウィンドウに追加
            window.offerLast(value);
            
            // 現在のウィンドウの内容を表示
            System.out.println("現在のウィンドウ: " + window);
            
            // 必要に応じてウィンドウ内の要素を処理
            // 例: ウィンドウ内の平均値を計算
            double average = window.stream().mapToInt(Integer::intValue).average().orElse(0);
            System.out.println("ウィンドウ内の平均値: " + average);
        }
    }
}

4. 両方向イテレーション

Deque は、descendingIterator() メソッドを使用して逆順にイテレーションすることもできます。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

public class DequeIterationExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.add("最初");
        deque.add("中間");
        deque.add("最後");
        
        // 通常の順序でイテレーション（先頭から末尾）
        System.out.println("通常順:");
        for (String item : deque) {
            System.out.println(item);
        }
        
        // 逆順でイテレーション（末尾から先頭）
        System.out.println("逆順:");
        Iterator<String> reverseIterator = deque.descendingIterator();
        while (reverseIterator.hasNext()) {
            System.out.println(reverseIterator.next());
        }
    }
}

パフォーマンスに関する考慮事項

ArrayDeque の最適化

初期容量の指定: 要素数が予測できる場合は、初期容量を指定することでリサイズのオーバーヘッドを減らせます。
removeFirstOccurrence/removeLastOccurrence の使用を最小限に: これらの操作は O(n) の時間計算量を持ちます。
contains メソッドの使用に注意: 要素の検索は O(n) の時間がかかります。

Java 8以降の Stream API との連携

Deque も他のコレクションと同様に Stream API と組み合わせて使用できます。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.stream.Collectors;

public class DequeStreamExample {
    public static void main(String[] args) {
        Deque<Integer> numbers = new ArrayDeque<>();
        numbers.addAll(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
        
        // 偶数のみをフィルタリングして新しいリストを作成
        List<Integer> evenNumbers = numbers.stream()
                .filter(n -> n % 2 == 0)
                .collect(Collectors.toList());
        // [2, 4, 6, 8, 10]
        
        // 各要素を2倍にして合計を計算
        int sum = numbers.stream()
                .mapToInt(n -> n * 2)
                .sum();
        // 110
        
        // 5より大きい最初の3つの要素を取得
        List<Integer> firstThreeGreaterThanFive = numbers.stream()
                .filter(n -> n > 5)
                .limit(3)
                .collect(Collectors.toList());
        // [6, 7, 8]
    }
}

まとめ

Queue と Deque インターフェースは、特定の順序で要素を処理する必要がある場合に非常に便利なコレクションです。主な実装である ArrayDeque と LinkedList はそれぞれ異なる特性を持っており、用途に応じて適切に選択することが重要です。

ArrayDeque: 一般的なスタックやキューの実装として最適で、メモリ効率が良く、高速な操作を提供します。
LinkedList: リスト操作とDeque操作の両方が必要な場合や、null要素を格納する必要がある場合に適しています。

多くの場合、ArrayDeque がデフォルトの選択肢として適しています。特定のユースケースで LinkedList が明確な利点を提供する場合にのみ、LinkedList の使用を検討してください。