La structure de données de type pile (Stack) est un composant fondamental en informatique, offrant des opérations telles que l'insertion (push), la suppression (pop) et la consultation de l'élément au sommet (top), le tout avec une complexité temporelle de O(1). Cependant, un besoin fréquent dans diverses applications, comme l'évaluation d'expressions ou certains algorithmes de piles monotones, est de pouvoir récupérer le minimum actuel de la pile en temps constant.

Une implémentation naïve de cette fonctionnalité consisterait à parcourir tous les éléments de la pile à chaque requête de minimum, ce qui dégraderait la performance à O(n), où 'n' est le nombre d'éléments. Pour des ensembles de données volumineux, cette approche est inefficace. L'objectif est donc de concevoir une structure de pile modifiée, souvent appelée "pile minimale" (MinStack), permettant à l'opération getMin d'atteindre également une complexité de O(1).

Stratégie Fondamentale : L'Approche à Double Pile

Pour graantir un accès O(1) au minimum, la clé réside dans la maintenance proactive de cette valeur. Nous utilisons une pile auxiliaire qui fonctionne en conjonction avec la pile principale, s'assurant que le sommet de la pile auxiliaire représente toujours le minimum actuel de la pile principale.

Répartition des Rôles entre les Piles

• Pile Principale (pileContenu) : Elle stocke tous les éléments ajoutés et gère les opérations classiques d'une pile (empiler, dépiler, consulter le sommet).
• Pile des Minimums (pileMinAuxiliaire) : Cette pile ne contient que les minimums "stade par stade". Son sommet pointe toujours vers la plus petite valeur présente dans la pileContenu.

Règles Essentielles de Synchronisation

Les opérations de la pile auxiliaire doivent suivre des règles strictes pour que son sommet reste toujours le minimum global :

1. Opération empiler (push) :
   • L'élément est d'abord inséré dans la pileContenu.
   • Si la pileMinAuxiliaire est vide, ou si le nouvel élément est inférieur ou égal au sommet de la pileMinAuxiliaire, alors cet élément est également inséré dans la pileMinAuxiliaire. L'utilisation de "inférieur ou égal" est cruciale pour gérer les cas de valeurs minimales dupliquées et éviter de perdre le minimum.
2. Opération depiler (pop) :
   • Avant de retirer un élément, on vérifie si le sommet de la pileContenu est identique au sommet de la pileMinAuxiliaire. Si c'est le cas, cela signifie que le minimum actuel est sur le point d'être retiré, et la pileMinAuxiliaire doit être synchronisée en dépilant son propre sommet.
   • Ensuite, l'élément au sommet de la pileContenu est retiré.
3. Opération obtenirMinimum (getMin) : Le sommet de la pileMinAuxiliaire est simplement retourné. Cette valeur est garantie d'être le minimum actuel.
4. Opération sommet (top) : Le sommet de la pileContenu est retourné, comme pour une pile standard.

Implémentation en C++ avec Double Pile

Voici une implémentation de la pile minimale utilisant deux piles standards C++.

#include <stack> // Nécessaire pour std::stack
#include <algorithm> // Nécessaire pour std::min, bien que non utilisé dans cette version

class PileAvecMinimum {
private:
    // Pile principale : stocke tous les éléments
    std::stack<int> pileDonnees;
    // Pile auxiliaire : stocke les minimums successifs
    // Le sommet de cette pile est toujours le minimum actuel de pileDonnees
    std::stack<int> pileMinAuxiliaire;

public:
    // Constructeur : initialise les piles (fait par défaut pour std::stack)
    PileAvecMinimum() {
        // Les constructeurs par défaut de std::stack gèrent l'initialisation.
    }
    
    // Ajoute un élément à la pile
    void empiler(int valeur) {
        // 1. Ajouter l'élément à la pile principale
        pileDonnees.push(valeur);
        
        // 2. Mettre à jour la pile des minimums si nécessaire
        //    L'élément est ajouté si pileMinAuxiliaire est vide
        //    OU si l'élément est inférieur ou égal au minimum actuel.
        if (pileMinAuxiliaire.empty() || valeur <= pileMinAuxiliaire.top()) {
            pileMinAuxiliaire.push(valeur);
        }
    }
    
    // Retire l'élément du sommet de la pile
    void depiler() {
        // Vérifier si la pile principale n'est pas vide avant de dépiler
        if (pileDonnees.empty()) {
            // Optionnel: lever une exception ou gérer l'erreur
            return; 
        }

        // Si l'élément à dépiler de la pile principale est le minimum actuel,
        // il faut aussi le dépiler de la pile des minimums.
        if (pileDonnees.top() == pileMinAuxiliaire.top()) {
            pileMinAuxiliaire.pop();
        }
        
        // Dépiler l'élément de la pile principale
        pileDonnees.pop();
    }
    
    // Retourne l'élément au sommet de la pile principale
    int sommet() {
        if (pileDonnees.empty()) {
            // Optionnel: lever une exception ou retourner une valeur par défaut
            throw std::runtime_error("La pile est vide.");
        }
        return pileDonnees.top();
    }
    
    // Retourne le minimum actuel de la pile
    int obtenirMinimum() {
        if (pileMinAuxiliaire.empty()) {
            // Optionnel: lever une exception ou retourner une valeur par défaut
            throw std::runtime_error("La pile est vide, pas de minimum.");
        }
        return pileMinAuxiliaire.top();
    }
};

Éclaircissements sur les Choix de Conception

1. Pourquoi "inférieur ou égal" lors de l'empiler ? Imaginez une séquence d'insertion : 2 → 2.
   • Si nous n'ajoutions que les éléments "strictement inférieurs" : Le premier 2 irait dans pileMinAuxiliaire. Le second 2 ne serait pas ajouté (car il n'est pas < au sommet de pileMinAuxiliaire). Lorsque le premier 2 est retiré de la pile principale, pileMinAuxiliaire serait aussi dépilée, devenant vide. La pile principale contiendrait encore 2, mais obtenirMinimum échouerait ou serait incorrect.
   • En utilisant "inférieur ou égal", les deux 2 seraient stockés dans pileMinAuxiliaire. Le minimum resterait correct même après le dépilement du premier 2.
2. Pourquoi dépiler la pile des minimums avant la pile principale ? C'est l'inverse : on dépile la pile principale, mais on vérifie d'abord si son sommet correspond au minimum actuel (sommet de pileMinAuxiliaire). Si la pile principale était dépilée en premier, nous perdrions la valeur de son sommet et ne pourrions plus faire la comparaison nécessaire pour savoir si pileMinAuxiliaire doit être mise à jour.

Analyse de Complexité

• Complexité Temporelle : Toutes les opérations fondamentales (push, pop, top des piles internes) sont en temps constant O(1).
• Complexité Spatiale : Dans le pire des cas (par exemple, si les éléments sont insérés en ordre strictement décroissant : 5→4→3→2→1), la pileMinAuxiliaire peut stocker autant d'éléments que la pileContenu. La complexité spatiale est donc O(n), où 'n' est le nombre d'éléments dans la pile principale.

Alternative : L'Approche à Pile Unique

Une autre technique pour construire une pile minimale utilise une seule pile qui stocke des paires d'éléments. Chaque élément de la pile est une paire (valeur_actuelle, minimum_jusqu_ici).

Exemple d'Implémentation en C++ (Pile Unique)

#include <stack>
#include <utility> // Nécessaire pour std::pair
#include <algorithm> // Nécessaire pour std::min

class PileMinimaleCompacte {
private:
    // Pile stockant des paires {valeur de l'élément, minimum à ce point de la pile}
    std::stack<std::pair<int, int>> pileElementsEtMin;

public:
    PileMinimaleCompacte() {}
    
    // Ajoute un élément
    void ajouter(int element) {
        if (pileElementsEtMin.empty()) {
            // Si la pile est vide, l'élément est son propre minimum
            pileElementsEtMin.push({element, element});
        } else {
            // Le nouveau minimum est le minimum entre l'élément actuel et le minimum précédent
            int nouveauMin = std::min(element, pileElementsEtMin.top().second);
            pileElementsEtMin.push({element, nouveauMin});
        }
    }
    
    // Retire l'élément au sommet
    void retirer() {
        if (pileElementsEtMin.empty()) {
            throw std::runtime_error("La pile est vide.");
        }
        pileElementsEtMin.pop();
    }
    
    // Retourne la valeur au sommet de la pile
    int voirSommet() {
        if (pileElementsEtMin.empty()) {
            throw std::runtime_error("La pile est vide.");
        }
        return pileElementsEtMin.top().first; // 'first' est l'élément lui-même
    }
    
    // Retourne le minimum actuel
    int trouverMinimum() {
        if (pileElementsEtMin.empty()) {
            throw std::runtime_error("La pile est vide.");
        }
        return pileElementsEtMin.top().second; // 'second' est le minimum à ce point
    }
};

Comparaison des Deux Approches

Le choix entre ces deux méthodes dépend souvent des contraintes spécifiques du projet : si l'optimisation spatiale est cruciale dans certains scénarios (par exemple, si les valeurs empilées sont fréquemment croissantes), la double pile peut être préférée. Si la simplicité et la compacité du code sont prioritaires, l'approche à pile unique est une excellente option.