JavaDequeとスタック

投稿日: 2022-10-25 2022-10-25
タグ: Java Collections

1. 概要

Java Stack クラスは、スタックデータ構造を実装します。 Java 1.6では、 Deque インターフェースが導入されました。これは、両端での要素の挿入と削除をサポートする「両端キュー」を実装するためのものです。

これで、 Deque インターフェイスをLIFO（後入れ先出し）スタックとしても使用できるようになりました。さらに、Stackクラスの Javadocを見ると、次のことがわかります。

より完全で一貫性のあるLIFOスタック操作のセットは、 Deque インターフェイスとその実装によって提供されます。これらは、このクラスよりも優先して使用する必要があります。

このチュートリアルでは、Java StackクラスとDequeインターフェースを比較します。さらに、LIFOスタックにDequeoverStackを使用する必要がある理由についても説明します。

2. クラス対。インターフェース

Javaのスタックはクラスです：

public class Stack<E> extends Vector<E> { ... }

つまり、独自の Stack タイプを作成する場合は、java.util.Stackクラスを継承する必要があります。

Javaは多重継承をサポートしていないため、クラスがすでに別のタイプのサブクラスである場合、Stackクラスを拡張するのが難しい場合があります：

public class UserActivityStack extends ActivityCollection { ... }

上記の例では、UserActivityStackクラスはActivityCollectionクラスのサブクラスです。したがって、java.util.Stackクラスを拡張することもできません。 Java Stack クラスを使用するには、データモデルを再設計する必要がある場合があります。

一方、JavaのDequeはインターフェイスです。

public interface Deque<E> extends Queue<E> { ... }

クラスがJavaで複数のインターフェースを実装できることはわかっています。したがって、インターフェイスの実装は、継承のためにクラスを拡張するよりも柔軟性があります。

たとえば、UserActivityStackにDequeインターフェイスを簡単に実装させることができます。

public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }

したがって、オブジェクト指向設計の観点からは、DequeインターフェースはStackクラスよりも柔軟性があります。

3. 同期メソッドとパフォーマンス

Stackクラスはjava.util.Vectorのサブクラスであることがわかりました。 Vectorクラスが同期されます。スレッドセーフを実現するために従来の方法を使用します。つまり、メソッドを「同期します。」にします。

そのサブクラスとして、Stackクラスも同期されます。

一方、Dequeインターフェースはスレッドセーフではありません。

したがって、スレッドセーフが要件でない場合、Dequeはスタックよりも優れたパフォーマンスをもたらすことができます。

4. 反復順序

StackとDequeはどちらもjava.util.Collectionインターフェースのサブタイプであるため、Iterableでもあります。

ただし、興味深いのは、同じ要素を同じ順序でStackオブジェクトとDequeインスタンスにプッシュすると、それらの反復順序が異なることです。

例を通してそれらを詳しく見てみましょう。

まず、いくつかの要素を Stack オブジェクトにプッシュして、その反復順序を確認しましょう。

@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the bottom.",
      "I am in the middle.",
      "I am at the top.");
}

上記のテストメソッドを実行すると、合格します。つまり、 Stackオブジェクトの要素を反復処理すると、スタックの下部からスタックの上部の順序になります。

次に、Dequeインスタンスで同じテストを実行してみましょう。テストでは、ArrayDequeクラスをDeque実装として使用します。

また、ArrayDequeをLIFOスタックとして使用します。

@Test
void givenADeque_whenIterate_thenFromTopToBottom() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the top.",
      "I am in the middle.",
      "I am at the bottom.");
}

このテストは、実行すれば合格します。

したがって、Dequeの反復順序は上から下です。

LIFOスタックのデータ構造について話しているとき、スタック内の要素を反復処理する適切な順序は上から下にある必要があります。

つまり、 Deque のイテレータは、スタックに期待するとおりに機能します。

5. 無効なLIFOスタック操作

従来のLIFOスタックデータ構造は、 push（）、 pop（）、および peek（）操作のみをサポートします。 StackクラスとDequeインターフェースの両方がそれらをサポートします。ここまでは順調ですね。

ただし、 LIFOルールに違反するため、LIFOスタック内のインデックスによる要素へのアクセスまたは操作は許可されていません。

このセクションでは、StackおよびDeque。を使用して無効なスタック操作を呼び出すことができるかどうかを確認しましょう。

5.1. java.util.Stackクラス

親のVectorは配列ベースのデータ構造であるため、Stackクラスにはインデックスによって要素にアクセスする機能があります。

@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element."); //index 0
    myStack.push("I am the 2nd element."); //index 1
    myStack.push("I am the 3rd element."); //index 2
 
    assertThat(myStack.get(0)).isEqualTo("I am the 1st element.");
}

テストを実行すると合格します。

テストでは、3つの要素をStackオブジェクトにプッシュします。その後、スタックの一番下にある要素にアクセスします。

LIFOルールに従って、下の要素にアクセスするには、上のすべての要素をポップする必要があります。

ただし、ここでは、 Stackオブジェクトを使用して、そのインデックスで要素にアクセスできます。

さらに、 Stack オブジェクトを使用すると、インデックスによって要素を挿入および削除することもできます。それを証明するためのテストメソッドを作成しましょう。

@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(2);

    myStack.add(1, "I am the 2nd element.");
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(myStack.get(1)).isEqualTo("I am the 2nd element.");

    myStack.remove(1);
    assertThat(myStack.size()).isEqualTo(2);
}

テストを実行すると、テストにも合格します。

したがって、 Stack クラスを使用すると、配列を操作するのと同じように、その中の要素を操作できます。これはLIFO契約を破りました。

5.2. java.util.Dequeインターフェース

Dequeでは、インデックスによって要素にアクセス、挿入、または削除することはできません。それはより良い音スタッククラス。

ただし、 Deque は「両端キュー」であるため、両端から要素を挿入または削除できます。

つまり、 DequeをLIFOスタックとして使用すると、スタックの最下部に直接要素を挿入/削除できます。

これがどのように行われるかを確認するためのテストメソッドを作成しましょう。繰り返しになりますが、テストではArrayDequeクラスを引き続き使用します。

@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 2nd element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(3);

    //insert element to the bottom of the stack
    myStack.addLast("I am the NEW element.");
    assertThat(myStack.size()).isEqualTo(4);
    assertThat(myStack.peek()).isEqualTo("I am the 3rd element.");

    //remove element from the bottom of the stack
    String removedStr = myStack.removeLast();
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(removedStr).isEqualTo("I am the NEW element.");
}

テストでは、最初に、 addLast（）メソッドを使用して、スタックの一番下に新しい要素を挿入します。挿入が成功した場合、 removeLast（）メソッドを使用して挿入を削除しようとします。

テストを実行すると合格です。

したがって、DequeはLIFOコントラクトにも従いません。

5.3. Dequeに基づくLifoStackの実装

LIFO契約に従うための単純なLifoStackインターフェースを作成できます。

public interface LifoStack<E> extends Collection<E> {
    E peek();
    E pop();
    void push(E item);
}

LifoStack インターフェースの実装を作成する場合、Java標準のDeque実装をラップできます。

簡単に理解できるように、例としてArrayLifoStackクラスを作成しましょう。

public class ArrayLifoStack<E> implements LifoStack<E> {
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        return deque.removeFirst();
    }

    @Override
    public E peek() {
        return deque.peekFirst();
    }

    // forward methods in Collection interface
    // to the deque object

    @Override
    public int size() {
        return deque.size();
    }
...
}

ArrayLifoStack クラスが示すように、LifoStackインターフェースとjava.util.Collectionインターフェースで定義された操作のみをサポートします。

このようにして、LIFOルールに違反することはありません。

6. 結論

Java 1.6以降、java.util.Stackとjava.util.Dequeの両方をLIFOスタックとして使用できます。この記事では、これら2つのタイプの違いについて説明しました。

また、LIFOスタックを操作するためにStackクラスでDequeインターフェイスを使用する必要がある理由も分析しました。

さらに、例で説明したように、StackとDequeはどちらも、多かれ少なかれLIFOルールに違反しています。

最後に、LIFOコントラクトに従うスタックインターフェイスを作成する1つの方法を示しました。

いつものように、完全なソースコードはGitHubでから入手できます。

getdocs

13036