Java -Programm, um die Elemente des Stapels in absteigender Reihenfolge zu sortieren

Dieser Artikel zeigt, wie die Elemente eines Stacks in absteigender Reihenfolge mit Java sortiert werden. Ein Stapel, der das LEFO-Prinzip (Last-In-First-Out) festhält, ist eine grundlegende Datenstruktur. Denken Sie an die Geschichte eines Browsers. Die zuletzt besuchte Website wird zuerst zugegriffen. Wir werden eine rekursive Java -Lösung für diese Sortieraufgabe untersuchen.

Problem:

ordnen Sie seine Elemente in absteigender Reihenfolge an (größtes Element oben).

Eingabebeispiel:

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

Ausgabebeispiel:

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

rekursive Java -Lösung:

Unser Ansatz verwendet Rekursion, um den Stapel effizient zu sortieren. Der Prozess umfasst folgende Schritte:

1. sortStack(Stack<integer> stack)</integer> Methode: Diese rekursive Methode entfernt iterativ Elemente aus dem Eingabestapel, bis sie leer ist. Jedes entferntes Element wird vorübergehend gespeichert, und die sortStack -Methode ruft sich rekursiv auf dem verbleibenden Stapel auf.

2. sortedInsert(Stack<integer> stack, int element)</integer> Helfermethode: Diese Methode behandelt die Einführung der vorübergehend entfernten Elemente wieder in den Stapel und hält die absteigende Reihenfolge bei. Es prüft, ob der Stapel leer ist oder ob das zu eingefügte Element größer ist als das aktuelle obere Element. Wenn eine der beiden Bedingungen wahr ist, wird das Element auf den Stapel gedrückt. Andernfalls wird das obere Element vorübergehend entfernt, sortedInsert rekursiv aufgerufen, und dann wird das vorübergehend entfernte Element zurückgedrückt.

3. Hauptmethode: Die main -Methode erstellt einen Beispielstapel, ruft sortStack auf, um ihn zu sortieren, und druckt dann den sortierten Stapel.

Hier ist der vollständige Java -Code:

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);
    }
}

Ausgabe:

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

Zeit- und Raumkomplexität:

• Zeitkomplexität: o (n ² ), wobei n die Anzahl der Elemente im Stapel ist. Dies ist auf die verschachtelte Art der rekursiven Anrufe zurückzuführen.
• Raumkomplexität: o (n) aufgrund des rekursiven Anrufstapels.

Dieser rekursive Ansatz bietet eine klare und prägnante Lösung, um einen Stapel in absteigender Reihenfolge in Java zu sortieren. Die Verwendung einer Helferfunktion verbessert die Code -Lesbarkeit und -organisation.

Das obige ist der detaillierte Inhalt vonJava -Programm, um die Elemente des Stapels in absteigender Reihenfolge zu sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!