Programme Java pour trouver les éléments maximum et minimum dans une pile

La pile

est une structure de données de base qui suit le dernier principe de premier out (également connu sous le nom de LIFO). Il existe de nombreux cas d'utilisation pour la pile, tels que l'organisation des appels de fonction et des opérations d'annulation. Souvent, on peut rencontrer le problème de la recherche des éléments les plus importants et les plus petits de la pile, et cet article démontrera plusieurs façons d'accomplir cette tâche en utilisant Java.

Comprendre la pile

La pile

est une structure de données linéaire qui permet les opérations à une extrémité, appelée le haut. Les principales opérations comprennent:

• push (push) : ajouter des éléments en haut de la pile.
• pop (pop) : supprime et revient à l'élément supérieur de la pile.
• View (peek) : Affichez l'élément supérieur de la pile sans le retirer.
• iSempty (iSempty) : Vérifiez si la pile est vide.

Instruction Problème

L'objectif est de déterminer les éléments maximum et minimum dans la pile. Compte tenu de la nature LIFO de la pile, des éléments autres que le haut ne sont pas accessibles directement. Cela nécessite de traverser la pile tout en gardant une trace des valeurs maximales et minimales.

Utilisez deux variables supplémentaires

Ici, nous utilisons deux variables min et max pour suivre respectivement les valeurs minimales et maximales. Itérer sur la pile et mettre à jour ces variables au fur et à mesure que chaque élément est traité. Il s'agit de la méthode la plus simple et la méthode la plus longue et la plus chronométrée.

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

sortie

Éléments maximaux: 30 Élément minimum: 5

en utilisant la pile auxiliaire

Ici, nous traversons la pile en utilisant une opération pop-up et à la mise à jour des valeurs minimales et maximales au besoin. La pile auxiliaire enregistre temporairement des éléments, puis restaure ces éléments à la pile d'origine.

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

sortie

Éléments maximaux: 30 Élément minimum: 5

Utilisez deux piles

Cette méthode utilise deux piles supplémentaires, l'une pour se souvenir du plus grand élément (maxStack) et l'autre pour se souvenir du plus petit élément (minStack). Chaque fois qu'un nouvel élément pénètre dans la pile principale, si elle rend la valeur maximale ou minimale plus grande, nous la mettons également dans maxStack ou minStack.

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

sortie

Éléments maximaux: 30 Élément minimum: 5

Utilisez la structure de pile modifiée

La structure de pile est modifiée pour inclure les valeurs maximales et minimales et les éléments de pile réguliers en lui-même. Chaque élément est enregistré en paire contenant la valeur, la valeur maximale actuelle et la valeur minimale actuelle.

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

sortie

Éléments maximaux: 30 Élément minimum: 5

Conclusion

La recherche des éléments les plus importants et les plus petits de la pile peut être résolu de différentes manières, chacune avec ses avantages et ses inconvénients. Les méthodes indiquées incluent l'utilisation de variables supplémentaires, les piles auxiliaires, la gestion de piles séparées pour des valeurs maximales et minimales ou la modification de la structure de la pile elle-même.

Chaque technologie fournit un moyen spécifique de gérer les éléments d'accès ou d'enregistrement de la pile, ce qui le rend adapté à certaines situations en fonction des limitations de la mémoire, des exigences de performance et des exigences d'intégrité des données. La compréhension et l'application de ces méthodes peuvent aider les développeurs à gérer efficacement les piles en Java, ce qui rend leurs applications les mieux adaptées à certaines situations.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!