Javaのスタックからすべての要素を削除します

このチュートリアルでは、Javaスタックから均等数を排除する2つの方法を示しています。 最後のファーストアウト（LIFO）の原則に準拠したスタックは、このタイプのフィルタリングに対するユニークな課題を提示します。 ここに示す手法は、偶数を削除するだけでなく、他のフィルタリングシナリオに適応できます。

問題：

整数のスタックを与えられて、すべての偶数を削除するためにJavaプログラムを書いてください。

入力と出力の例：

入力1：
• 出力1：[1, 2, 3, 4, 5] [1, 3, 5]
入力2：
• output 2：[1, 7, 3, 11, 9]（均一な数字は削除されません） [1, 7, 3, 11, 9]

ソリューションアプローチ：

2つの異なるアプローチを調べます：

1. 補助スタックを使用してください：

   この方法は、オリジナルのスタックを繰り返しながら奇数を保存するために一時的なスタックを使用します。

2. 再帰の使用：

   この再帰アプローチは、スタックを効率的に処理し、再帰通話中に偶数を削除します。

メソッド1：補助スタック

このアプローチには、これらの手順が含まれます

一時的な

（例えば、

）を作成します。

1. 元のスタックを繰り返し、各要素をポップします。Stack tempStack要素が奇数の場合（Modulo演算子を使用して
を使用してチェック）、
2. 。
に押します
3. 元のスタックが空になったら、%から元のスタックに戻る要素を転送します。 tempStack
4. コードの例（補助スタック）：tempStack

時間と空間の複雑さ（補助スタック）：

import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<Integer> stack) {
        Stack<Integer> tempStack = new Stack<>();
        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (element % 2 != 0) {
                tempStack.push(element);
            }
        }
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}

時間の複雑さ：o（n） - スタックを2回繰り返します。

スペースの複雑さ：
• o（n） - 入力スタックと同じサイズの潜在的に同じサイズの補助スタックを使用します。
メソッド2：再帰
• この再帰ソリューションは、偶数の削除をエレガントに処理します：

ベースケース：スタックが空の場合は、戻ります。 上部の要素をポップします。

残りのスタックを処理するために

関数を再帰的に呼び出します。

再帰コールの後、ポップされた要素が奇妙であるかどうかを確認します。もしそうなら、それをスタックに押し戻します。
コードの例（再帰）：
3. removeEven
時間と空間の複雑さ（再帰）：

時間の複雑さ：

import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int element = stack.pop();
        removeEven(stack);
        if (element % 2 != 0) {
            stack.push(element);
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}

o（n） - スタックを再帰的に横断します。

スペースの複雑さ：

o（n） - 再帰コールスタックは、最悪の場合に入力スタックのサイズに成長できます。

• 結論：

両方の方法は、スタックから偶数の数値を効果的に削除します。補助スタックアプローチはより簡単ですが、再帰的アプローチはより簡潔で潜在的にわずかに効率的なソリューションを提供します（JVMの最適化に応じて）。 選択は、個人的な好みとコーディングスタイルに依存します。 これらの手法は、さまざまな基準に基づいてスタックをフィルタリングするように適合させることができることを忘れないでください。

以上がJavaのスタックからすべての要素を削除しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。