特定のスタックの上部と下部の要素を見つけるためのJavaプログラム

このチュートリアルでは、Javaを使用して特定のスタックの上部と下部要素を見つける方法を説明します。

スタックは、最初のout（lifo）原理の最後のに続く線形データセットを表します。したがって、同じ場所で要素が追加および削除されます。さらに、特定のスタックの上部と下部の要素を見つけるための2つの方法を探ります。つまり、およびを反復します。 問題声明

n要素を含むスタックアレイが取得されます。タスクは、スタックの1番目とn番目の要素を何らかの形で破壊することなく見つけることです。したがって、元のスタックが変更されていないことを確認するには、カスタムスタックで

反復方法

および再帰的方法を使用する必要があります。

1

を入力します

<code>stack = [5, 10, 15, 20, 25, 30]</code>

出力1

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

2 出力2

<code>stack = [1000, 2000, 3000, 4000, 5000]</code>

上部および下部要素を見つけるための反復方法

最初の方法では、スタックとして使用される配列を定義し、スタック操作を定義して、反復方法で目的の要素を取得します。特定のスタックの上部と下部要素を見つけるための手順は次のとおりです。

<code>堆栈元素：5000 4000 3000 2000 1000
底部元素：1000
顶部元素：5000</code>

a

maxsize

値が6に等しく、上部を-1に設定してスタックを初期化します（空の配列を表します）。

• 要素5、10、15、20、25、および30を押して30プッシュ（）操作でスタックに押し込み、StackArray [TOP]で最高値を増やします。 スタックが空であるかどうかを確認します。次に、
peek（）
• を使用して、StackArray [Top]を返すことで上部要素を見つけます。 最後に、bottom（）関数
• を使用します。 最終的な上部と下の値を出力します。
• 例
以下は、反復方法を使用して特定のスタックの上部と下部要素を見つけるJavaプログラムです。
output

時間の複雑さ：スタック形成中の

o（n）は、各要素が配列の端に追加され、インデックスはサイズnまで毎回1ずつ増加するためです。 o（1）は、覗き式および下部操作中に、stackarray [top]とstackarray [0]を返すためです。

class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    // 使用MyStack构造函数初始化堆栈
    public MyStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];

        // 将Top变量初始化为-1，表示空堆栈
        this.top = -1;
    }
    // 将元素添加到stackArray中
    public void push(int value) {
        if (top < maxSize -1) {
            stackArray[++top] = value;
        } else {
            System.out.println("堆栈已满");
        }
    }
    // 使用peek()查找顶部元素
    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println("堆栈为空。");
            return -1;
        }
    }
    // 使用bottom()查找堆栈数组中的底部元素（第一个添加的值）
    public int bottom() {
        if (top >= 0) {
            return stackArray[0];
        } else {
            System.out.println("堆栈为空。");
            return -1;
        }
    }
}
public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack(6); // 创建大小为6的堆栈
        // 将元素压入堆栈
        stack.push(5);
        stack.push(10);
        stack.push(15);
        stack.push(20);
        stack.push(25);
        stack.push(30);
        // 检索顶部和底部元素
        int topElement = stack.peek();
        int bottomElement = stack.bottom();
        // 打印最终输出
        System.out.println("堆栈中的顶部元素是 --> " + topElement);
        System.out.println("堆栈中的底部元素是 --> " + bottomElement);
    }
}

スペースの複雑さ：

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

o（n）。マックスサイズを修正して、スタックのサイズに比例してn要素を保存するためです。

上部および下部の要素を見つけるための再帰的な方法 このアプローチでは、再帰を使用して、スタック内の上部と下部の要素を見つけます。スタックは初期化され、push（）操作を使用して形成され、必要な要素を再帰的に抽出します。特定のスタックの上部と下部要素を見つけるための手順は次のとおりです。

• maxsize を使用してスタックを初期化します。これは5に等しく、トップセットは-1になります。
• スタックサイズがMaxSizeを超えないかどうかを確認します。 push（）関数を使用して、各整数値をスタックに押し、1倍に増分し、値をstackarray [top]に保存します。
• 再帰的な方法を使用して下位要素を見つけ、現在のインデックスを最上位値に設定します。次に、インデックスが0の場合、 stackArray [0] （下部要素）、それ以外の場合は、関数はインデックスが1によって減少する場合に再帰的に呼ばれます。
• インデックスを0に設定した上部要素を見つけます。基本的なケースでは、現在のインデックスが最高値に等しい場合、stackArray [top] が返されます。それ以外の場合、関数は1で増分するインデックスを使用して再帰的に呼ばれます。
• すべての要素を再帰的に印刷してStackArray []、基本的なケースは、インデックスが0未満の場合、再帰が停止することです。それ以外の場合は、関数を呼び出して、整数値を再帰的に印刷して、インデックスが減少しました。
• メイン関数を呼び出し、上部と下の要素とスタック全体を印刷します。

例

以下は、再帰的な方法を使用して特定のスタックの上部と下部要素を見つけるJavaプログラムです。

<code>stack = [5, 10, 15, 20, 25, 30]</code>

output

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

時間の複雑さ：合計はO（n）です。これは、要素がサイズnのスタック形成中にo（1）操作にo（1）を費やすためです。最悪の場合、再帰操作コストo（n）。

空間的な複雑さ：再帰コールスタックのため、再帰的にはO（n）です。アレイ自体は、o（n）を使用してn要素を保存します。

結論

要するに、どちらの方法もそれぞれのケースに適用できます。このケースでは、直接配列メソッドはスタック要素とその単純なインタラクティブな実装への絶え間ない時間アクセスを提供します。一方、再帰的な方法は、スタック操作に関する再帰的な視点を提供し、それらをより一般的にし、アルゴリズム方法を強調します。これらの2つの方法を理解することで、スタックの基本と、どちらの方法を使用するかを使用することができます。

以上が特定のスタックの上部と下部の要素を見つけるためのJavaプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。