Javaスタック

Java におけるスタックとは、通常、List インターフェースを実装する Collection Framework のクラスを意味します。これは、メモリのタイプの 1 つを編成するために使用されるスタックデータ構造の原理に基づいて機能します。また、データを保持するメモリの一部である可能性もあります。この記事では、まずStackクラスに注目し、そのメソッドを検討し、例を示します。ただし、スタックのようなデータ構造とその用途についても説明します。

スタックデータ構造とは

まず、スタックデータ構造が何であるかを簡単に見てみましょう。これは、後入れ先出し (LIFO) 原則に基づいた線形データ構造です。それは一種のアンチキューです。トランプのデッキや箱に入った本の山を想像してください。最初に積み重ねた本が一番下にあり、最初に箱から取り出すのは一番上にあった本、つまり最後に箱に入った本です。この原理を示す gif 画像を次に示します。 Java スタック - 1

何が起きてる？一度に 1 つのボールしか打てないフラスコがあります。フラスコの最初のボールはオレンジ色のボールで、次に紫色、そして最後に緑色になります (これらの色のより正確な名前を知っている方には申し訳ありません)。ただし、フラスコのスタックからオレンジ色のボールを抽出するには、最初に最後に到着したボール (緑色のボール) を抽出し、次に最後から 2 番目のボールを抽出する必要があります (ただし、抽出時点では最後です)。一）。Java またはその他のプログラミングにおけるスタックデータ構造には、pushとPop という2 つの最も重要な操作があります。プッシュ操作はスタックに要素を挿入し、ポップ操作はスタックの先頭から要素を削除します。

スタックのデータ構造は何のためにあるのでしょうか?

スタックの最も重要な用途の 1 つは、サブルーチン呼び出しを整理することです。スタック上の呼び出しポイントには、サブルーチン終了後のリターンアドレス (および場合によっては渡されたパラメーター) が格納されます。サブルーチンのネストされた (再帰を含む) 呼び出しごとに、新しいリターンアドレスがスタックに追加されます。サブルーチンからの戻り操作 (return) ごとに、戻りアドレスがスタックから削除され、制御がスタックに転送されます。このアプリケーションはプログラミングにとって非常に重要であるため、ほとんどのプロセッサではリターンスタックが命令セットのハードウェアに実装されています。ただし、他の場合には、スタックをより一般的なデータ構造に基づいてモデル化する必要があります。

コレクションフレームワークのJavaスタッククラス

Java では、Stackクラスは、List インターフェイスを実装し、Vector クラスを拡張する Collection フレームワークのクラスです。また、インターフェイス Collection、Iterable、Cloneable、Serializable も実装します。おそらくすでにご想像のとおり、このクラスはオブジェクトの LIFO スタックを表します。ここでは、 Stackクラスのコンストラクターの呼び出し、つまり、このクラスのオブジェクトの作成を示します。

Stack<E> stack = new Stack<E>();

ここで、E はオブジェクトのタイプです。

Java スタックメソッド

このクラスには、デフォルトのコンストラクターが 1 つだけあり、 Vectorクラスのすべてのメソッドが含まれます。さらに、Stack には独自の 5 つのメソッドがあります。

boolean empty()このメソッドはスタックが空かどうかをチェックします。スタックが空の場合はtrueを返し、そうでない場合はfalseを返します。
Object Peak()メソッドは、スタックの最上位にある要素を返します。
Object Pop()メソッドはスタックの最上位にある要素を返し、それを削除します。
Object Push(Object element)このメソッドは、指定された要素をスタックの先頭に追加します。
int search(Object element)このメソッドは、指定された要素をスタックから検索します。必要な要素が見つかった場合は、その先頭からの「距離」(通し番号)を返します。要素が見つからない場合は、-1 が返されます。

スタックコードの例

上のgif画像のような動作するプログラム例を作成してみましょう。オレンジ、紫、緑の 3 つの「ボール」をスタックに置きます。スタックが空かどうかを確認してみましょう。次に、スタックが空になるまでスタックからボールを取り出します。

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

このプログラムの出力は次のとおりです。

私のスタックは空ですか? スタック内の真の要素: [オレンジボール、バイオレットボール、グリーンボール] 私のスタックは空ですか? false スタック内の要素: [オレンジボール、バイオレットボール] スタックは空ですか? false スタック内の要素: [オレンジボール] スタックは空ですか? false スタック内の要素: [] スタックは空ですか? 真実

StackはVectorクラスから継承され、Listインターフェイスを実装しているため、Stack には、要素を追加および抽出するためのこのデータ構造に対する従来のプッシュおよびポップ操作に加えて、リスト構造のadd()およびdelete()操作の標準もあります。この例では、要素の追加はadd()メソッドを使用して同じ方法で実装できます。ただし、 remove()を使用して抽出できるのは要素を指定した場合のみであり、スタックデータ構造にとっては意味がありません。

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

もちろん、プログラムの作業の結果はまったく同じになります。

独自のスタック実装についてはどうですか?

配列またはリンクリストクラスを使用して、Java で独自のスタックデータ構造を作成できます。最初のケースでは、セルの連続配列がメモリに値を保存するために割り当てられ、必要に応じて使用されます。2 番目では、スタックの要素ごとに、値とスタックの前後の要素への参照を格納するのに十分なメモリブロックが順序付けされます。配列ベースの実装は、よりシンプルで効率的でメモリ効率も高くなりますが、スタックサイズの制限についての事前の知識が必要であり、見つけにくいバグが発生する可能性があります。リストベースの実装はより堅牢ですが、効率は低くなります。スタックの単純な配列ベースの実装を作成してみましょう。機能も含まれます。

Push — 要素を(先頭の位置に)確実に追加するメソッド
Pop — 要素を（先頭の位置から）削除するメソッド
readTop — 先頭の位置にある要素の値を返すメソッド
sEmpty — スタックが空かどうかをチェックするメソッド
isFull — スタックを格納する配列がいっぱいかどうかをチェックするメソッド

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

次に、スタックに基づいて 3 つのボールを含む例を実装してみましょう。

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

出力は次のとおりです。

私のスタックは空ですか? true [オレンジボール、バイオレットボール、グリーンボール] 私のスタックは空ですか? false 緑色のボールを削除しています私のスタックは空ですか? false バイオレットボールを削除しています私のスタックは空ですか? false オレンジボールを削除しています私のスタックは空ですか? 真実

よく見ると、実際には一番上の変数には最後の要素のインデックスが含まれており、オブジェクトへの参照は配列内に残っています。したがって、この実装にはいくつかの改善が必要です。これを行う最も簡単な方法を考えてください。

Java スタックを使用する必要がありますか?

実際、 Java Stack は、そのVector親と同様、レガシークラスです。代わりに、通常はArrayListクラスが使用されます。Vectorは同期されていますが、ArrayListは同期されません。つまり、Vectorでは一度に 1 つのスレッドのみがコードにアクセスできますが、ArrayList は複数のスレッドで動作できます。また、ArrayList はより効率的かつ高速です。したがって、このクラスは従来のコードでのみ使用される可能性が高くなります。ただし、スタックデータ構造はプログラミングで非常に頻繁に使用されます。