Java Academy · レッスン

Deque の操作：スタックとキュー

LinkedList を Deque として使用し、スタック（push/pop）とキュー（offer/poll）の動作を実装します。

「Deque の操作：スタックとキュー」はCoddyKit上の無料Java Academyレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

Deque：両端キュー

Deque（両端キュー）では、両端で要素を挿入・削除できます。Java の Deque インターフェースは、LinkedList と ArrayDeque によって実装されています。

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

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

Deque としての ArrayDeque と LinkedList の比較

Deque として使用する場合、一般的に ArrayDeque が LinkedList より推奨されます：

要素ごとのノードオーバーヘッドがありません
キャッシュ局所性に優れています
スタック・キュー操作がやや高速です

List インターフェースも必要な場合に限り、LinkedList を選択します。

Deque によるスタック操作

LIFO スタックを再現するには、push（addFirst）と pop（removeFirst）を使用します。従来の Stack クラスは同期化されていて古いため、使用を避けてください。

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Deque によるキュー操作

FIFO キューを再現するには、offer（addLast）と poll（removeFirst）を使用します。offer は失敗時に false を返しますが、add は例外をスローします。

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.size());  // 1

Deque のメソッド対応表

Deque には 2 つのメソッド群があります。一方は例外をスローし、もう一方は特殊な値を返します：

addFirst/addLast と offerFirst/offerLast
removeFirst/removeLast と pollFirst/pollLast
getFirst/getLast と peekFirst/peekLast

空の deque で例外が発生するのを避けるには、offer/poll/peek 系のメソッドを優先してください。

実例：2 つのスタックによる Undo/Redo

Deque の典型的な使用例です。Undo の履歴を 1 つのスタックで管理し、Redo をもう 1 つのスタックで管理します。

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Deque による回文チェック

Deque を使うと、両端から同時に文字を比較できるため、回文チェックを簡潔に実装できます。

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

キューによる BFS

幅優先探索（Breadth-First Search）ではキューを使用します。ArrayDeque は、競技プログラミングやグラフ走査で BFS に使用する標準的な選択肢です。

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

スタックによる DFS

深さ優先探索（Depth-First Search）ではスタックを使用します。ここでも、従来の Stack クラスより ArrayDeque を優先してください。

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

サイズチェックによる有界 Deque

ArrayDeque は動的に拡張されますが、容量を手動で制限すれば、有界バッファを再現できます：

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

パフォーマンスに関する注意点

ArrayDeque は、満杯になると 2 倍に拡張される循環配列を使用します。すべての操作の償却計算量は O(1) です。キャッシュ効率が高いため、ほとんどのベンチマークで LinkedList を上回ります。手動で同期を行わず、並行処理には ConcurrentLinkedDeque またはブロッキングキューを使用してください。

クイックチェック

LIFO 操作では、従来の Stack よりどのクラスを優先すべきですか？

まとめ：Deque の操作

重要なポイント：

Deque では両端での挿入・削除を O(1) で行えます
純粋なスタック・キュー用途では、LinkedList より ArrayDeque が推奨されます
push/pop → LIFO スタック、offer/poll → FIFO キュー
代表的な用途：Undo/Redo、BFS/DFS、スライディングウィンドウ、回文チェック
従来の Stack クラスと Queue クラスは避けてください

よくある質問

「Deque の操作：スタックとキュー」レッスンは無料ですか？

はい。「Deque の操作：スタックとキュー」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「Deque の操作：スタックとキュー」で何を学びますか？

LinkedList を Deque として使用し、スタック（push/pop）とキュー（offer/poll）の動作を実装します。ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン2/4です。

「Deque の操作：スタックとキュー」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Java Academyに戻る