JavaArrayDequeの概要

投稿日: 2019-10-18 2022-10-17
タグ: Java

1. 概要

このチュートリアルでは、JavaのArrayDequeクラスの使用方法を示します。これはDequeインターフェイスの実装です。

ArrayDeque （「ArrayDouble Ended Queue」とも呼ばれ、「ArrayDeck」と発音）は、両側から要素を追加または削除できる特殊な種類の拡張可能な配列です。

ArrayDeque 実装は、 Stack （後入れ先出し）または Queue （先入れ先出し）として使用できます。

2. APIの概要

操作ごとに、基本的に2つのオプションがあります。

最初のグループは、操作が失敗した場合に例外をスローするメソッドで構成されています。もう一方のグループは、ステータスまたは値を返します。

手術	方法	例外をスローするメソッド
頭からの挿入	オファーファースト（e）	addFirst（e）
頭からの取り外し	pollFirst（）	removeFirst（）
頭からの検索	peekFirst（）	getFirst（）
尾からの挿入	offerLast（e）	addLast（e）
尾からの除去	pollLast（）	removeLast（）
テールからの取得	peekLast（）	getLast（）

3. メソッドの使用

ArrayDequeを利用する方法の簡単な例をいくつか見てみましょう。

**3.1. ArrayDequeをスタックとして使用する**

クラスをStackとして扱う方法の例から始め、要素をプッシュします。

@Test
public void whenPush_addsAtFirst() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.getFirst());
}

ArrayDeque から要素をポップする方法も見てみましょう–スタックとして使用する場合：

@Test
public void whenPop_removesLast() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");
 
    assertEquals("second", stack.pop());
}

pop メソッドは、スタックが空の場合にNoSuchElementExceptionをスローします。

**3.2. ArrayDequeをキューとして使用する**

ここで、 ArrayDeque で要素を提供する方法を示す簡単な例から始めましょう–単純な Queueとして使用する場合：

@Test
public void whenOffer_addsAtLast() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("second", queue.getLast());
}

また、 Queue として使用する場合にも、ArrayDequeから要素をポーリングする方法を見てみましょう。

@Test
public void whenPoll_removesFirst() {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("first");
    queue.offer("second");
 
    assertEquals("first", queue.poll());
}

poll メソッドは、キューが空の場合、null値を返します。

**4. ArrayDequeの実装方法**

内部的には、 ArrayDequeは、いっぱいになるとサイズが2倍になる配列に支えられています。

最初に、配列はサイズ16で初期化されます。これは、ヘッドとテールの2つのポインターを維持する両端キューとして実装されます。

このロジックの動作を大まかに見てみましょう。

**4.1. ArrayDeque as Stack**

ご覧のとおり、ユーザーが push メソッドを使用して要素を追加すると、ヘッドポインターが1つ移動します。

要素をポップすると、その要素がヘッド位置にある null に設定されるため、要素はガベージコレクションされ、ヘッドポインターが1つ戻ります。

**4.2. ArrayDequeをキューとして**

offer メソッドを使用して要素を追加すると、テールポインターが1つ移動します。

一方、ユーザーが要素をポーリングすると、ヘッド位置の要素がnullに設定され、要素がガベージコレクションされる可能性があります。その後、ヘッドポインターが移動します。

**4.3. ArrayDequeに関する注意**

最後に、この特定の実装について理解し、覚えておく価値のあるいくつかのメモ：

スレッドセーフではありません
ヌル要素は受け入れられません
同期されたスタックよりも大幅に高速に動作します
参照の局所性が優れているため、LinkedListよりも高速なキューです
ほとんどの操作は、一定時間の複雑さを償却しています
ArrayDequeによって返されるIteratorはフェイルファストです
ArrayDeque は、要素の追加中にヘッドポインターとテールポインターが互いに一致すると、配列のサイズを自動的に2倍にします。

5. 結論

この短い記事では、ArrayDequeのメソッドの使用法を説明しました。

これらすべての例の実装は、GitHubプロジェクトにあります。これはMavenベースのプロジェクトであるため、そのままインポートして実行するのは簡単です。

getdocs

13036