Supprimez tous les éléments même d'une pile à Java

Ce tutoriel montre deux méthodes pour éliminer les nombres uniformes d'une pile Java. Les piles, adhérant au dernier principe de sortie (LIFO), présentent un défi unique pour ce type de filtrage. Les techniques montrées ici sont adaptables à d'autres scénarios de filtrage au-delà de simplement éliminer les nombres.

Le problème:

Compte tenu d'une pile d'entiers, écrivez un programme Java pour supprimer tous les nombres pair.

Exemples d'entrées et de sorties:

• Entrée 1: [1, 2, 3, 4, 5] Sortie 1: [1, 3, 5]
• Entrée 2: [1, 7, 3, 11, 9] Sortie 2: [1, 7, 3, 11, 9] (pas de nombres même à supprimer)

Approches de la solution:

Nous explorerons deux approches distinctes:

1. à l'aide d'une pile auxiliaire: Cette méthode utilise une pile temporaire pour stocker des nombres impairs tout en itérant à travers la pile d'origine.

2. Utilisation de la récursivité: Cette approche récursive traite efficacement la pile, en supprimant même les nombres pendant les appels récursifs.

Méthode 1: pile auxiliaire

Cette approche implique ces étapes:

1. Créez un Stack temporaire (par exemple, tempStack).
2. itérer à travers la pile d'origine, en éclatant chaque élément.
3. Si l'élément est impair (vérifiez en utilisant l'opérateur modulo %), poussez-le sur tempStack.
4. Une fois que la pile d'origine est vide, transférez les éléments de tempStack à la pile d'origine.

Exemple de code (pile auxiliaire):

<code class="language-java">import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<integer> stack) {
        Stack<integer> tempStack = new Stack<>();
        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (element % 2 != 0) {
                tempStack.push(element);
            }
        }
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }

    public static void main(String[] args) {
        Stack<integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}</integer></integer></integer></code>

Complexité du temps et de l'espace (pile auxiliaire):

• Complexité temporelle: o (n) - Nous itraquons à travers la pile deux fois.
• Complexité de l'espace: o (n) - Nous utilisons une pile auxiliaire potentiellement de la même taille que la pile d'entrée.

Méthode 2: Recursion

Cette solution récursive gère élégamment l'élimination du nombre uniforme:

1. Case de base: si la pile est vide, retournez.
2. éclater l'élément supérieur.
3. Appelez récursivement la fonction removeEven pour traiter la pile restante.
4. Après l'appel récursif, vérifiez si l'élément éclaté est étrange. Si c'est le cas, repoussez-le sur la pile.

Exemple de code (Recursion):

<code class="language-java">import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int element = stack.pop();
        removeEven(stack);
        if (element % 2 != 0) {
            stack.push(element);
        }
    }

    public static void main(String[] args) {
        Stack<integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}</integer></integer></code>

Complexité du temps et de l'espace (récursivité):

• Complexité temporelle: o (n) - Nous traversons récursivement la pile.
• Complexité de l'espace: o (n) - La pile d'appels récursive peut atteindre la taille de la pile d'entrée dans le pire des cas.

Conclusion:

Les deux méthodes suppriment efficacement les nombres même d'une pile. L'approche de la pile auxiliaire est plus simple, tandis que l'approche récursive offre une solution plus concise et potentiellement légèrement plus efficace (selon l'optimisation du JVM). Le choix dépend de la préférence personnelle et du style de codage. N'oubliez pas que ces techniques peuvent être adaptées pour filtrer les piles en fonction de divers critères.

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!