1概要

このチュートリアルでは、

Deque

インターフェースの実装であるJavaの

ArrayDeque

クラスの使い方を説明します。


ArrayDeque

(「Array Double Ended Queue」とも呼ばれ、「ArrayDeck」と発音されます)

は、両側から要素を追加または削除できる特殊な拡張可能配列です。


ArrayDeque

実装は、

Stack

(後入れ先出し)または

Queue

(先入れ先出し)として使用できます。


2 APIの概要

各操作には、基本的に2つの選択肢があります。

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

| =================================================== == |操作|メソッド|例外をスローするメソッド|先頭からの挿入|

offerFirst(e)

|

addFirst(e)

|先頭からの削除|

pollFirst()

|

removeFirst()

|先頭からの検索|

peekFirst()

|

getFirst()

| Tailからの挿入|

offerLast(e)

|

addLast(e)

| Tailからの削除|

pollLast()

|

removeLast()

| Tailからの検索|

peekLast()

|

getLast()

| = ====================================================

** 3メソッドを使う


ArrayDeque

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


3.1.

Stack


として

ArrayDeque

を使用する

クラスを

Stack

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

@Test
public void whenPush__addsAtFirst() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("first");
    stack.push("second");

    assertEquals("second", stack.getFirst());
}

また、Stackとして使用した場合に

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.

Queue


として

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

はどのように実装されていますか


/uploads/ArrayDeque.jpg

フードの下では、**

ArrayDeque

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

最初、配列は16のサイズで初期化されます。これは、2つのポインタ、つまり先頭と末尾を保持する両端キューとして実装されています。

この論理を実際に見てみましょう – 高レベルで。


4.1. スタックとしての

ArrayDeque



/uploads/Stack.jpg

ご覧のとおり、ユーザーが

push

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

要素をポップすると、要素は先頭位置の

null

に設定されるため、要素はガベージコレクションされ、その後、先頭のポインタが1つ戻ります。


4.2.

Queue


としての

ArrayDeque


/uploads/Queue.jpg


offer

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

ユーザーが要素をポーリングするときには、その要素がガベージコレクションされる可能性があるように、先頭位置の要素をnullに設定してから、ヘッドポインタを移動します。


4.3.

ArrayDeque


に関するメモ

最後に、この特定の実装について理解し、覚えておく価値がある、さらにいくつかの注意事項があります。

  • スレッドセーフではありません

  • null要素は受け入れられません

  • 同期された

    Stack

    よりもかなり速く動作します

  • のローカリティが高いため、

    LinkedList

    より速いキューです。

参照
** ほとんどの業務は一定時間の複雑さを償却しました


  • ArrayDeque

    によって返された

    Iterator

    は、非常に高速です。


  • ArrayDeque

    は、先頭と末尾の配列のサイズを自動的に2倍にします。

要素を追加しながらテールポインタが互いに会う


5結論

この短い記事では、

ArrayDeque

のメソッドの使い方を説明しました。

これらすべての例の実装はhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[GitHubプロジェクト]にあります。これはMavenベースのプロジェクトなので、そのままインポートして実行するのは簡単なはずです。