スタックの要素を降順で並べ替えるためのJavaプログラム

この記事では、Javaを使用してStackの要素を降順で並べ替える方法を示しています。 最後のファーストアウト（LIFO）の原則に準拠したスタックは、基本的なデータ構造です。 ブラウザの歴史を考えてください。最近訪問されたサイトに最初にアクセスされます。 この並べ替えタスクのための再帰的なJavaソリューションを探索します。

問題：

整数の整理されていないスタックを与えられた場合、その要素を下降順に配置します（上部で最大の要素）。

入力例：

<code>Original Stack: [4, 2, 9, 7]</code>

出力の例：

<code>Sorted Stack in Descending Order: [9, 7, 4, 2]</code>

再帰的なJavaソリューション：

私たちのアプローチは、スタックを効率的にソートするために再帰を採用しています。このプロセスには、これらの手順が含まれます

1. メソッド：

   この再帰メソッドは、空になるまで入力スタックから要素を繰り返し削除します。 削除された各要素は一時的に保存され、メソッドは残りのスタックに再帰的に自らを呼び出します。 sortStack(Stack<integer> stack)</integer> sortStack

ヘルパーメソッド：
2. このメソッドは、一時的に削除された要素の挿入をスタックに戻し、下降順序を維持します。 スタックが空であるかどうか、または挿入する要素が現在の上部要素よりも大きいかどうかを確認します。いずれかの条件が真である場合、要素はスタックに押し込まれます。それ以外の場合、上部の要素が一時的に削除され、

   が再帰的に呼び出され、一時的に削除された要素が押し戻されます。 sortedInsert(Stack<integer> stack, int element)</integer> sortedInsertメイン方法：

メソッドはサンプルスタックを作成し、
3. を呼び出してソートしてから、ソートされたスタックを印刷します。

   これが完全なJavaコードです：main sortStack

output：

import java.util.Stack;

public class StackSorter {

    public static void sortStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            int top = stack.pop();
            sortStack(stack);
            sortedInsert(stack, top);
        }
    }

    public static void sortedInsert(Stack<Integer> stack, int element) {
        if (stack.isEmpty() || element > stack.peek()) {
            stack.push(element);
            return;
        }
        int temp = stack.pop();
        sortedInsert(stack, element);
        stack.push(temp);
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(4);
        stack.push(2);
        stack.push(9);
        stack.push(7);

        System.out.println("Original Stack: " + stack);
        sortStack(stack);
        System.out.println("Sorted Stack in Descending Order: " + stack);
    }
}

時間と空間の複雑さ：

<code>Original Stack: [4, 2, 9, 7]
Sorted Stack in Descending Order: [9, 7, 4, 2]</code>

時間の複雑さ：o（n 2

）、nはスタック内の要素の数です。これは、再帰的な呼び出しのネストされた性質によるものです。

• スペースの複雑さ： o（n）再帰コールスタックによる ^{この再帰的アプローチは、Javaでスタックを降順で並べ替えるための明確で簡潔なソリューションを提供します。 ヘルパー関数を使用すると、コードの読みやすさと組織が向上します。}

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