[Java] ArrayDequeの使い方 – 両端キュークラス

ArrayDequeは、Javaで提供される両端キュー(デック)を実装するクラスです。

ArrayDequeは、スタックやキューとして使用でき、両端から要素の追加や削除が可能です。

ArrayDequeは内部的に配列を使用しており、サイズが自動的に拡張されます。

主なメソッドには、addFirst()やaddLast()で要素を追加し、removeFirst()やremoveLast()で要素を削除するものがあります。

ArrayDequeはnull要素を許容しない点に注意が必要です。

この記事でわかること

ArrayDequeの基本操作と使い方
スタックやキューとしての活用法
パフォーマンス特性と計算量
制約や注意点についての理解
実際の応用例を通じた活用方法

目次から探す

ArrayDequeとは

ArrayDequeは、Javaのコレクションフレームワークに含まれるデータ構造で、両端キュー(Deque)を実装しています。

これは、要素を両端から追加・削除できる特性を持ち、スタックやキューとしても利用可能です。

ArrayDequeは、内部的に可変長の配列を使用しており、要素の追加や削除が高速に行えるため、パフォーマンスに優れています。

また、スレッドセーフではないため、複数のスレッドから同時にアクセスする場合は注意が必要です。

ArrayDequeは、特にデータの先頭や末尾に頻繁にアクセスする必要がある場合に便利です。

ArrayDequeの基本操作

ArrayDequeでは、要素の追加、削除、取得を簡単に行うことができます。

以下に、基本的な操作について詳しく説明します。

要素の追加

addFirst()とaddLast()の使い方

addFirst()メソッドは、指定した要素をDequeの先頭に追加します。

一方、addLast()メソッドは、指定した要素をDequeの末尾に追加します。

これらのメソッドは、要素の追加に成功した場合はtrueを返します。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        // 先頭に要素を追加
        deque.addFirst("先頭の要素");
        // 末尾に要素を追加
        deque.addLast("末尾の要素");
        System.out.println(deque);
    }
}

[先頭の要素, 末尾の要素]

offerFirst()とofferLast()の違い

offerFirst()メソッドは、要素を先頭に追加し、追加に成功した場合はtrueを返します。

offerLast()メソッドも同様に、要素を末尾に追加しますが、こちらも成功した場合はtrueを返します。

これらのメソッドは、容量制限がある場合に、追加できない場合はfalseを返す点が特徴です。

要素の削除

removeFirst()とremoveLast()の使い方

removeFirst()メソッドは、Dequeの先頭から要素を削除し、その要素を返します。

Dequeが空の場合は、NoSuchElementExceptionがスローされます。

removeLast()メソッドも同様に、末尾から要素を削除します。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addFirst("先頭の要素");
        deque.addLast("末尾の要素");
        // 先頭の要素を削除
        String firstElement = deque.removeFirst();
        // 末尾の要素を削除
        String lastElement = deque.removeLast();
        System.out.println("削除した先頭の要素: " + firstElement);
        System.out.println("削除した末尾の要素: " + lastElement);
    }
}

削除した先頭の要素: 先頭の要素
削除した末尾の要素: 末尾の要素

pollFirst()とpollLast()の違い

pollFirst()メソッドは、先頭の要素を削除し、その要素を返しますが、Dequeが空の場合はnullを返します。

pollLast()メソッドも同様に、末尾の要素を削除しますが、こちらも空の場合はnullを返します。

これにより、例外を避けることができます。

要素の取得

getFirst()とgetLast()の使い方

getFirst()メソッドは、Dequeの先頭の要素を取得しますが、Dequeが空の場合はNoSuchElementExceptionがスローされます。

getLast()メソッドも同様に、末尾の要素を取得します。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addFirst("先頭の要素");
        deque.addLast("末尾の要素");
        // 先頭の要素を取得
        String firstElement = deque.getFirst();
        // 末尾の要素を取得
        String lastElement = deque.getLast();
        System.out.println("先頭の要素: " + firstElement);
        System.out.println("末尾の要素: " + lastElement);
    }
}

先頭の要素: 先頭の要素
末尾の要素: 末尾の要素

peekFirst()とpeekLast()の違い

peekFirst()メソッドは、先頭の要素を取得しますが、Dequeが空の場合はnullを返します。

peekLast()メソッドも同様に、末尾の要素を取得しますが、こちらも空の場合はnullを返します。

これにより、例外を避けつつ、要素を確認することができます。

ArrayDequeの応用操作

ArrayDequeは、スタックやキューとしても利用できる柔軟なデータ構造です。

以下に、具体的な応用操作について説明します。

スタックとしての使用

ArrayDequeは、スタックとしての操作もサポートしています。

スタックは、LIFO(Last In, First Out)方式で要素を管理します。

push()とpop()の使い方

push()メソッドは、要素をスタックの先頭に追加します。

pop()メソッドは、先頭の要素を削除し、その要素を返します。

これにより、スタックの基本的な操作が実現できます。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> stack = new ArrayDeque<>();
        // 要素をスタックに追加
        stack.push("要素1");
        stack.push("要素2");
        // 要素をスタックから削除
        String poppedElement = stack.pop();
        System.out.println("削除した要素: " + poppedElement);
        System.out.println("スタックの内容: " + stack);
    }
}

削除した要素: 要素2
スタックの内容: [要素1]

キューとしての使用

ArrayDequeは、キューとしての操作もサポートしています。

キューは、FIFO(First In, First Out)方式で要素を管理します。

offer()とpoll()の使い方

offer()メソッドは、要素をキューの末尾に追加します。

poll()メソッドは、先頭の要素を削除し、その要素を返します。

これにより、キューの基本的な操作が実現できます。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> queue = new ArrayDeque<>();
        // 要素をキューに追加
        queue.offer("要素1");
        queue.offer("要素2");
        // 要素をキューから削除
        String polledElement = queue.poll();
        System.out.println("削除した要素: " + polledElement);
        System.out.println("キューの内容: " + queue);
    }
}

削除した要素: 要素1
キューの内容: [要素2]

イテレーション

ArrayDequeは、要素を簡単に反復処理することができます。

for-eachループでの使用

for-eachループを使用して、ArrayDeque内のすべての要素を簡単に表示できます。

import java.util.ArrayDeque;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.add("要素1");
        deque.add("要素2");
        deque.add("要素3");
        // for-eachループで要素を表示
        for (String element : deque) {
            System.out.println("要素: " + element);
        }
    }
}

要素: 要素1
要素: 要素2
要素: 要素3

Iteratorを使ったループ処理

Iteratorを使用することで、より柔軟な反復処理が可能です。

特に、要素を削除しながら反復処理を行う場合に便利です。

import java.util.ArrayDeque;
import java.util.Iterator;
public class App {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.add("要素1");
        deque.add("要素2");
        deque.add("要素3");
        // Iteratorを使って要素を表示
        Iterator<String> iterator = deque.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println("要素: " + element);
            // 条件に応じて要素を削除
            if (element.equals("要素2")) {
                iterator.remove(); // 要素2を削除
            }
        }
        System.out.println("残った要素: " + deque);
    }
}

要素: 要素1
要素: 要素2
要素: 要素3
残った要素: [要素1, 要素3]

ArrayDequeのパフォーマンス

ArrayDequeは、効率的なデータ構造として設計されており、さまざまな操作において高いパフォーマンスを発揮します。

以下に、ArrayDequeのパフォーマンスに関する詳細を説明します。

ArrayDequeの時間計算量

ArrayDequeの主要な操作における時間計算量は以下の通りです。

スクロールできます

操作	時間計算量
要素の追加(addFirst, addLast)	O(1)
要素の削除(removeFirst, removeLast)	O(1)
要素の取得(getFirst, getLast)	O(1)
要素のイテレーション	O(n)

このように、ArrayDequeは要素の追加や削除において定数時間で処理を行うため、非常に効率的です。

ArrayDequeのメモリ効率

ArrayDequeは、内部的に可変長の配列を使用しており、必要に応じてサイズを自動的に拡張します。

これにより、メモリの使用効率が向上します。

ただし、配列のサイズが拡張される際には、既存の要素を新しい配列にコピーする必要があるため、一時的にメモリの使用量が増加することがあります。

また、ArrayDequeは、LinkedListに比べてメモリオーバーヘッドが少ないため、要素数が多い場合には特にメモリ効率が良いとされています。

ArrayDequeとLinkedListのパフォーマンス比較

ArrayDequeとLinkedListは、どちらもDequeインターフェースを実装していますが、それぞれ異なる特性を持っています。

以下に、両者のパフォーマンスを比較します。

スクロールできます

特徴	ArrayDeque	LinkedList
要素の追加	O(1)	O(1)
要素の削除	O(1)	O(1)
要素の取得	O(1)	O(n)
メモリ効率	高い(配列ベース)	低い(ノードベース)
スレッドセーフ性	スレッドセーフではない	スレッドセーフではない

ArrayDequeは、要素の取得においてLinkedListよりも優れたパフォーマンスを発揮しますが、LinkedListは要素の挿入や削除においても同様にO(1)の時間計算量を持っています。

選択する際は、使用するシナリオに応じて、どちらのデータ構造が適しているかを考慮することが重要です。

ArrayDequeの制約と注意点

ArrayDequeは非常に便利なデータ構造ですが、いくつかの制約や注意点があります。

以下に、主なポイントを説明します。

null要素の扱い

ArrayDequeは、null要素を追加することができません。

nullを追加しようとすると、NullPointerExceptionがスローされます。

このため、ArrayDequeを使用する際は、nullを要素として扱う必要がある場合は、他のデータ構造を検討するか、特別な処理を行う必要があります。

スレッドセーフではない点

ArrayDequeは、スレッドセーフではありません。

つまり、複数のスレッドから同時にアクセスする場合、データの整合性が保証されません。

スレッド間での競合状態を避けるためには、外部で同期処理を行う必要があります。

スレッドセーフなデータ構造が必要な場合は、ConcurrentLinkedDequeなどの他のクラスを使用することを検討してください。

サイズ制限のない点

ArrayDequeは、内部的に可変長の配列を使用しており、サイズ制限はありませんが、メモリが許す限り要素を追加できます。

ただし、配列のサイズが拡張される際には、既存の要素を新しい配列にコピーする必要があるため、大量の要素を追加する場合はパフォーマンスに影響を与える可能性があります。

また、メモリの使用量が増加するため、メモリ管理にも注意が必要です。

特に、大量のデータを扱う場合は、メモリの使用状況を監視することが重要です。

ArrayDequeの活用例

ArrayDequeは、その特性を活かしてさまざまな場面で利用されます。

以下に、具体的な活用例をいくつか紹介します。

ブラウザの履歴管理

ブラウザでは、ユーザーが訪れたページの履歴を管理するためにArrayDequeを利用することができます。

ユーザーが新しいページに移動するたびに、現在のページをDequeの先頭に追加し、戻る操作を行う際には先頭の要素を削除することで、簡単に履歴を管理できます。

import java.util.ArrayDeque;
public class BrowserHistory {
    private ArrayDeque<String> history = new ArrayDeque<>();
    public void visit(String url) {
        history.addFirst(url); // 新しいURLを履歴に追加
    }
    public String back() {
        return history.pollFirst(); // 最後に訪れたURLを取得して削除
    }
    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory();
        browser.visit("https://example.com");
        browser.visit("https://example.org");
        System.out.println("戻る: " + browser.back()); // https://example.org
    }
}

バックトラッキングアルゴリズム

バックトラッキングアルゴリズムでは、探索の過程での状態を管理するためにArrayDequeを使用することができます。

探索中に訪れたノードや状態をDequeに追加し、探索が失敗した場合にはDequeから要素を削除して元の状態に戻ることができます。

import java.util.ArrayDeque;
public class BacktrackingExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // 例として、1から5までの数を探索する
        for (int i = 1; i <= 5; i++) {
            stack.push(i); // 状態をスタックに追加
        }
        while (!stack.isEmpty()) {
            int current = stack.pop(); // 状態を取得して削除
            System.out.println("現在の状態: " + current);
        }
    }
}

BFS(幅優先探索)での使用

幅優先探索(BFS)アルゴリズムでは、探索するノードを管理するためにArrayDequeが非常に便利です。

キューとしての特性を活かし、ノードをDequeの末尾に追加し、先頭からノードを取り出して探索を進めることができます。

import java.util.ArrayDeque;
public class BFSExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(1); // ルートノードを追加
        while (!queue.isEmpty()) {
            int current = queue.poll(); // ノードを取得して削除
            System.out.println("訪問ノード: " + current);
            // 子ノードを追加(例として、現在のノードの子ノードを2と3とする)
            queue.offer(current * 2);
            queue.offer(current * 2 + 1);
        }
    }
}

これらの例からもわかるように、ArrayDequeはさまざまなアルゴリズムやデータ管理の場面で非常に役立つデータ構造です。

特に、要素の追加や削除が高速であるため、リアルタイム性が求められるアプリケーションにおいても効果的に利用できます。