Après avoir exploré les listes linéaires classiques, il est essentiel d'aborder une variante spécialisée : la Pile (Stack). Bien qu'il s'agisse techniquement d'une liste linéaire, elle se distingue par ses restrictions opérationnelles qui en font un outil pusisant pour de nombreux algorithmes système.

1. Concepts Fondamentaux

Une pile est une structure de données linéaire où l'ajout et la suppression d'éléments se font exclusivement à une seule extrémité, appelée le sommet (Top). L'autre extrémité est fixe et nommée la base (Bottom).

Cette restriction impose une discipline de gestion des données de type LIFO (Last In, First Out) : le dernier élément inséré est systématiquement le premier à être extrait. On utilise généralement les termes Empiler (Push) pour l'insertion et Dépiler (Pop) pour l'extraction.

Ordre de sortie et permutations

L'ordre des opérations influence directement la séquence de sortie. Par exemple, si nous insérons les nombres 1, 2 et 3 dans cet ordre, plusieurs séquences de sortie sont possibles selon le moment où les opérations de dépilage surviennent. Il existe exactement 5 combinaisons valides (calculables via les nombres de Catalan) :

• 3, 2, 1 (Tout empiler, puis tout dépiler)
• 1, 2, 3 (Empiler/Dépiler chaque élément immédiatement)
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1

Notez qu'une séquence comme 3, 1, 2 est impossible, car pour sortir le 3, le 1 et le 2 doivent déjà être dans la pile, imposant la sortie du 2 avant le 1.

2. Implémentation Séquentielle (Tableaux)

L'approche la plus simple consiste à utiliser un tableau de taille fixe. Un curseur (un entier) suit la position du sommet actuel.

#define CAPACITE_MAX 100

typedef struct {
   int donnees[CAPACITE_MAX];
   int index_sommet; // Initialisé à -1 pour une pile vide
} PileStatique;

// Opération d'insertion
bool pousser(PileStatique *p, int valeur) {
   if (p->index_sommet == CAPACITE_MAX - 1) {
       return false; // Pile pleine
   }
   p->index_sommet++;
   p->donnees[p->index_sommet] = valeur;
   return true;
}

// Opération d'extraction
bool retirer(PileStatique *p, int *valeur_extraite) {
   if (p->index_sommet == -1) {
       return false; // Pile vide
   }
   *valeur_extraite = p->donnees[p->index_sommet];
   p->index_sommet--;
   return true;
}

3. Optimisation : Double Pile Partagée

Pour optimiser l'espace mémoire lorsqu'on utilise deux piles de même type, on peut utiliser un seul tableau. La première pile commence à l'indice 0 et croît vers la droite, tandis que la seconde commence à l'extrémité finale et croît vers la gauche.

La condition de saturation est simple : index_sommet1 + 1 == index_sommet2. Cette structure est idéale lorsque l'une des piles se vide pendent que l'autre se remplit.

4. Implémentation Chaînée (Listes Liées)

La Pile Chaînée (LinkStack) élimine la contrainte de taille fixe. Chaque élément est un nœud pointant vers l'élément situé en dessous de lui. Le sommet est simplement le premier nœud de la liste.

typedef struct Noeud {
   int info;
   struct Noeud *suivant;
} Noeud;

typedef struct {
   Noeud *haut;
   int taille;
} PileDynamique;

void empiler_dynamique(PileDynamique *p, int valeur) {
   Noeud *nouveau = (Noeud*)malloc(sizeof(Noeud));
   nouveau->info = valeur;
   nouveau->suivant = p->haut;
   p->haut = nouveau;
   p->taille++;
}

int depiler_dynamique(PileDynamique *p) {
   if (p->haut == NULL) return -1;
   
   Noeud *cible = p->haut;
   int resultat = cible->info;
   p->haut = cible->suivant;
   free(cible);
   p->taille--;
   return resultat;
}

5. Applications Pratiques

La Récursion

La pile est au cœur du fonctionnement de la récursion dans les langages de programmation. Chaque appel de fonction génère un "cadre de pile" (stack frame) contenant les variables locales et l'adresse de retour. Prenons l'exemple de la suite de Fibonacci :

int fibonacci(int n) {
   if (n <= 1) return n;
   return fibonacci(n - 1) + fibonacci(n - 2);
}

Chaque appel suspendu est stocké dans la pile système jusqu'à ce que la condition d'arrêt soit atteinte.

Évaluation d'expressions arithmétiques

Les calculatrices utilisent souvent la Notation Polonaise Inverse (NPI) ou notation suffixe. Dans cette notation, l'opérateur suit ses opérandes (ex: 3 4 + au lieu de 3 + 4).

Algorithme de calcul NPI :

1. Pracourir l'expression de gauche à droite.
2. Si c'est un nombre : l'empiler.
3. Si c'est un opérateur : dépiler les deux derniers nombres, effectuer l'opération, et empiler le résultat.

Pour convertir une expression classique (infixe) en NPI, on utilise l'algorithme "Shunting-yard" qui s'appuie également sur une pile pour gérer la priorité des opérateurs et les parenthèses.