Programme Java pour trier les éléments de la pile dans l'ordre descendant

Cet article montre comment trier les éléments d'une pile dans l'ordre descendant à l'aide de Java. Une pile, adhérant au dernier principe de sortie (LIFO), est une structure de données fondamentale. Pensez à l'histoire d'un navigateur; Le site le plus récemment visité est accessible en premier. Nous explorerons une solution Java récursive pour cette tâche de tri.

Problème:

Compte tenu d'une pile d'entiers non triée, organisez ses éléments dans l'ordre descendant (le plus grand élément en haut).

Exemple d'entrée:

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

Exemple de sortie:

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

Solution Java récursive:

Notre approche utilise une récursivité pour trier efficacement la pile. Le processus implique ces étapes:

1. sortStack(Stack<integer> stack)</integer> Méthode: Cette méthode récursive supprime itérativement les éléments de la pile d'entrée jusqu'à ce qu'elle soit vide. Chaque élément supprimé est temporairement stocké et la méthode sortStack s'appelle récursivement sur la pile restante.

2. sortedInsert(Stack<integer> stack, int element)</integer> Méthode d'assistance: Cette méthode gère l'insertion des éléments retirés temporairement dans la pile, en maintenant l'ordre descendant. Il vérifie si la pile est vide ou si l'élément à insérer est supérieur à l'élément supérieur actuel. Si l'une ou l'autre condition est vraie, l'élément est poussé sur la pile. Sinon, l'élément supérieur est temporairement supprimé, sortedInsert est appelé récursivement, puis l'élément temporairement supprimé est repoussé.

3. Méthode principale: La méthode main crée une pile d'échantillons, appelle sortStack pour le trier, puis imprime la pile triée.

Voici le code Java complet:

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

Sortie:

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

Complexité du temps et de l'espace:

• Complexité temporelle: o (n ² ), où n est le nombre d'éléments dans la pile. Cela est dû à la nature imbriquée des appels récursifs.
• Complexité de l'espace: o (n) en raison de la pile d'appels récursive.

Cette approche récursive fournit une solution claire et concise pour trier une pile dans l'ordre descendant en Java. L'utilisation d'une fonction d'assistance améliore la lisibilité et l'organisation du code.

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!