Java -Programm, um die maximalen und minimalen Elemente in einem Stapel zu finden

Stack ist eine grundlegende Datenstruktur, die dem letzten ersten Out-Prinzip (auch als LIFO bekannt) folgt. Es gibt viele Anwendungsfälle für den Stapel, z. B. die Organisation von Funktionsaufrufen und das Rückgängigungsbetrieb. Oft kann man auf das Problem stoßen, die größten und kleinsten Elemente im Stapel zu finden, und dieser Artikel zeigt mehrere Möglichkeiten, diese Aufgabe mit Java zu erfüllen.

Stack verstehen

Stack ist eine lineare Datenstruktur, die Operationen nur an einem Ende ermöglicht, die als Top bezeichnet wird. Hauptvorgänge umfassen:

• drücken (drücken) : Fügen Sie Elemente an die Oberseite des Stapels hinzu.
• pop (pop) : Entfernt und kehrt zum oberen Element des Stapels zurück.
• Ansicht (Peek) : Zeigen Sie das obere Element des Stapels an, ohne ihn zu entfernen.
• isEmpty (isEmpty) : Überprüfen Sie, ob der Stapel leer ist.

Problemanweisung

Ziel ist es, die maximalen und minimalen Elemente im Stapel zu bestimmen. Angesichts der Lebensschärfe des Stapels können andere Elemente als die Oberseite nicht direkt zugegriffen werden. Dies erfordert das Durchqueren des Stapels und verfolgt gleichzeitig die maximalen und minimalen Werte.

Verwenden Sie zwei zusätzliche Variablen

Hier verwenden wir zwei Variablen min und max, um die minimalen und maximalen Werte zu verfolgen. Iterieren Sie den Stapel und aktualisieren Sie diese Variablen, sobald jedes Element verarbeitet wird. Dies ist die einfachste Methode und die zeitaufwändigste und räumlich-konsumierende Methode.

import java.util.Stack;

public class MaxMinInStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(5);
        stack.push(15);

        int[] result = findMaxMin(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static int[] findMaxMin(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (Integer element : stack) {
            if (element > max) {
                max = element;
            }
            if (element < min) {
                min = element;
            }
        }
        return new int[]{max, min};
    }
}

Ausgabe

Maximale Elemente: 30 Minimalelement: 5

Verwenden Sie den Hilfsstapel

Hier durchqueren wir den Stapel, indem wir einen Pop-up-Vorgang verwenden und die minimalen und maximalen Werte bei Bedarf aktualisieren. Der Hilfsstapel spart vorübergehend Elemente und stellt diese Elemente dann in den Originalstapel wieder her.

import java.util.Stack;

public class MaxMinInStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(5);
        stack.push(15);

        int[] result = findMaxMinWithAuxiliaryStack(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static int[] findMaxMinWithAuxiliaryStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        Stack<Integer> tempStack = new Stack<>();
        int max = stack.peek();
        int min = stack.peek();

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (current > max) {
                max = current;
            }
            if (current < min) {
                min = current;
            }
            tempStack.push(current);
        }

        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }

        return new int[]{max, min};
    }
}

Ausgabe

Maximale Elemente: 30 Minimalelement: 5

Verwenden Sie zwei Stapel

Diese Methode verwendet zwei zusätzliche Stapel, eine zum Erinnern an das größte Element (maxStack) und das andere zum Erinnern an das kleinste Element (minStack). Jedes Mal, wenn ein neues Element in den Hauptstapel eingeht, geben wir ihn auch in maxStack oder minStack in

oder ein.

import java.util.Stack;

public class MaxMinInStack {
    // ... (main method remains the same) ...

    public static int[] findMaxMinWithTwoStacks(Stack<Integer> stack) {
        Stack<Integer> maxStack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (maxStack.isEmpty() || current >= maxStack.peek()) {
                maxStack.push(current);
            }
            if (minStack.isEmpty() || current <= minStack.peek()) {
                minStack.push(current);
            }
        }
        return new int[]{maxStack.peek(), minStack.peek()};
    }
}

Ausgabe

Maximale Elemente: 30 Minimalelement: 5

Verwenden Sie die modifizierte Stapelstruktur

Die Stapelstruktur wird so modifiziert, dass sie die maximalen und minimalen Werte und regulären Stapelelemente in sich einbeziehen. Jedes Element wird als Paar gespeichert, das den Wert, den aktuellen Maximalwert und den aktuellen Mindestwert enthält.

import java.util.Stack;

public class MaxMinInStack {
    static class StackNode {
        int value;
        int currentMax;
        int currentMin;

        StackNode(int value, int currentMax, int currentMin) {
            this.value = value;
            this.currentMax = currentMax;
            this.currentMin = currentMin;
        }
    }

    public static void main(String[] args) {
        Stack<StackNode> stack = new Stack<>();
        push(stack, 10);
        push(stack, 20);
        push(stack, 30);
        push(stack, 5);
        push(stack, 15);

        int[] result = findMaxMinWithModifiedStack(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static void push(Stack<StackNode> stack, int value) {
        int max = stack.isEmpty() ? value : Math.max(value, stack.peek().currentMax);
        int min = stack.isEmpty() ? value : Math.min(value, stack.peek().currentMin);
        stack.push(new StackNode(value, max, min));
    }

    public static int[] findMaxMinWithModifiedStack(Stack<StackNode> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        StackNode topNode = stack.peek();
        return new int[]{topNode.currentMax, topNode.currentMin};
    }
}

Ausgabe

Maximale Elemente: 30 Minimalelement: 5

Schlussfolgerung

Auf der Suche nach den größten und kleinsten Elementen im Stapel kann auf unterschiedliche Weise gelöst werden, jeweils mit seinen Vor- und Nachteilen. Die gezeigten Methoden umfassen die Verwendung zusätzlicher Variablen, Hilfsstapel, die Verwaltung separater Stapel für maximale und minimale Werte oder das Ändern der Struktur des Stapels selbst.

Jede Technologie bietet eine spezifische Möglichkeit, Zugriffs- oder Speichern von Stapelelementen zu bewältigen, wodurch sie für bestimmte Situationen geeignet sind, die auf Speicherbeschränkungen, Leistungsanforderungen und Datenintegritätsanforderungen basieren. Das Verständnis und Anwenden dieser Methoden kann Entwicklern helfen, effektiv mit Stapeln in Java umzugehen, wodurch ihre Anwendungen für bestimmte Situationen am besten geeignet sind.

Das obige ist der detaillierte Inhalt vonJava -Programm, um die maximalen und minimalen Elemente in einem Stapel zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!