この記事では、Javaを使用してStackの要素を降順で並べ替える方法を示しています。 最後のファーストアウト(LIFO)の原則に準拠したスタックは、基本的なデータ構造です。 ブラウザの歴史を考えてください。最近訪問されたサイトに最初にアクセスされます。 この並べ替えタスクのための再帰的なJavaソリューションを探索します。
問題:
整数の整理されていないスタックを与えられた場合、その要素を下降順に配置します(上部で最大の要素)。 入力例:
<code>Original Stack: [4, 2, 9, 7]</code>
<code>Sorted Stack in Descending Order: [9, 7, 4, 2]</code>
私たちのアプローチは、スタックを効率的にソートするために再帰を採用しています。このプロセスには、これらの手順が含まれます
この再帰メソッドは、空になるまで入力スタックから要素を繰り返し削除します。 削除された各要素は一時的に保存され、メソッドは残りのスタックに再帰的に自らを呼び出します。
sortStack(Stack<integer> stack)</integer>
sortStack
が再帰的に呼び出され、一時的に削除された要素が押し戻されます。
sortedInsert(Stack<integer> stack, int element)</integer>
sortedInsert
メイン方法:
これが完全なJavaコードです:main
sortStack
<code class="language-java">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); } }</integer></integer></integer></code>
時間と空間の複雑さ:
<code>Original Stack: [4, 2, 9, 7] Sorted Stack in Descending Order: [9, 7, 4, 2]</code>
時間の複雑さ:o(n 2
)、nはスタック内の要素の数です。これは、再帰的な呼び出しのネストされた性質によるものです。以上がスタックの要素を降順で並べ替えるためのJavaプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。