Structure de données - Pile

Une pile est une structure de données linéaire qui suit le principe du dernier entré, premier sorti (LIFO). Elle peut être comprise de manière imagée comme une pile d’assiettes — vous ne pouvez en poser une que sur le dessus, et vous ne pouvez en prendre une que sur le dessus.

Concept et principe de la pile

Pile — Illustration du principe LIFO
Sommet — les opérations ne peuvent être effectuées qu’ici
Assiette 1 (Bas)
Assiette 2
Assiette 3
Assiette 4 (Sommet)
Bas — ne peut être retiré qu’en dernier
▲ push ▼ pop

Vérification LIFO : push 10→20→30, pop 30→20→10 (dernier entré, premier sorti) | La pile ne se préoccupe que du sommet, pas du milieu

Implémentation par tableau (pile séquentielle)

Stockage : tableau de taille fixe + pointeur de sommet

push : items[++top] = value

pop : return items[top--]

Avantages : accès rapide, adapté au cache, implémentation simple

Inconvénients : capacité fixe, peut déborder

Implémentation par liste chaînée (pile chaînée)

Stockage : nœuds dynamiques + pointeur de sommet (tête de liste chaînée)

push : méthode d'insertion en tête newNode->next = top

pop : top = top->next; free(old head)

Avantages : aucune limite de capacité, extension dynamique flexible

Inconvénients : surcoût de pointeur supplémentaire, peu adapté au cache

Implémentation de pile par tableau

Exemple

#include <stdio.h>
#include <stdbool.h> /* type booléen */

#define MAX_SIZE 100 /* Capacité maximale de la pile */

/* Structure de pile : contient un tableau de données et un pointeur de sommet */
struct Stack {
    int items[MAX_SIZE];  /* Tableau stockant les éléments de la pile */
    int top;              /* Pointeur de sommet, -1 signifie que la pile est vide */
};

/* Initialiser la pile : mettre top à -1 */
void initStack(struct Stack* s) {
    s->top = -1;
}

/* Vérifier si vide : la pile est vide lorsque top vaut -1 */
bool isEmpty(struct Stack* s) {
    return s->top == -1;
}

/* Vérifier si pleine : la pile est pleine lorsque top atteint la limite de capacité -1 */
bool isFull(struct Stack* s) {
    return s->top == MAX_SIZE - 1;
}

/* Empiler : placer un élément au sommet de la pile
D'abord déplacer top, puis écrire les données */
void push(struct Stack* s, int value) {
    if (isFull(s)) {
        printf("La pile est pleine, impossible d'empiler !\n");
        return;
    }
    s->items[++s->top] = value;  /* top est d'abord incrémenté de 1, puis on affecte value */
    printf("Empiler : %d\n", value);
}

/* Dépiler : retirer et renvoyer l'élément au sommet
D'abord récupérer les données, puis déplacer top */
int pop(struct Stack* s) {
    if (isEmpty(s)) {
        printf("La pile est vide, impossible de dépiler !"\n");
        return -1;  /* Retourne une valeur spéciale pour indiquer une erreur */
    }
    return s->items[s->top--];  /* Retourne d'abord la valeur, puis décrémente top */
}

/* Peek : ne dépile pas, consulte seulement le sommet */
int peek(struct Stack* s) {
    if (isEmpty(s)) {
        printf("La pile est vide !"\n");
        return -1;
    }
    return s->items[s->top];
}

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);  /* Empiler : 10 */
    push(&s, 20);  /* Empiler : 20 */
    push(&s, 30);  /* Empiler : 30 */

    printf("Élément au sommet : %d\n", peek(&s));  /* Sortie : élément au sommet : 30 */

    printf("Dépiler : %d\n", pop(&s));        /* Sortie : dépiler : 30 (dernier entré, premier sorti) */
    printf("Dépiler : %d\n", pop(&s));        /* Sortie : dépiler : 20 */
    printf("Dépiler : %d\n", pop(&s));        /* Sortie : dépiler : 10 */

    if (isEmpty(&s)) {
        printf("La pile est vide\n");                /* Sortie : la pile est vide */
    }
    return 0;
}

Implémentation d'une pile par liste chaînée

Exemple

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* Nœud de liste chaînée */
struct Node {
    int data;
    struct Node* next;
};

/* Empiler : utilise la tête de la liste chaînée comme sommet de la pile, méthode d'insertion en tête
Complexité temporelle : O(1) */
struct Node* push(struct Node* top, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;   /* Le nouveau nœud pointe vers le sommet original de la pile */
    printf("Empiler : %d\n", value);
    return newNode;          /* Le nouveau nœud devient le nouveau sommet de la pile */
}

/* Dépiler : supprimer le nœud de tête de la liste chaînée
Complexité temporelle : O(1) */
struct Node* pop(struct Node* top) {
    if (top == NULL) {
        printf("La pile est vide !"\n");
        return NULL;
    }
    struct Node* temp = top;
    printf("Dépilé : %d\n", top->data);
    top = top->next;   /* Déplacer top vers l'arrière */
    free(temp);         /* Libérer l'ancien sommet */
    return top;
}

/* Vérifier si vide */
bool isEmpty(struct Node* top) {
    return top == NULL;
}

int main() {
    struct Node* stackTop = NULL;  /* Initialement, la pile est vide */

    stackTop = push(stackTop, 100);  /* Empiler : 100 */
    stackTop = push(stackTop, 200);  /* Empiler : 200 */
    stackTop = push(stackTop, 300);  /* Empiler : 300 */

    printf("Sommet : %d\n", stackTop->data);  /* Sortie : Sommet : 300 */

    stackTop = pop(stackTop);  /* Dépiler : 300 */
    stackTop = pop(stackTop);  /* Dépiler : 200 */
    stackTop = pop(stackTop);  /* Dépiler : 100 */

    if (isEmpty(stackTop)) {
        printf("La pile est vide\n");      /* Sortie : La pile est vide */
    }
    return 0;
}

L'avantage d'implémenter une pile avec une liste chaînée est que, théoriquement, il n'y a pas de limite de capacité fixe, limitée uniquement par la mémoire disponible du système. Cependant, chaque nœud nécessite un espace de stockage supplémentaire pour le pointeur.

Scénarios d'application des piles

Scénarios d'applicationDescriptionPourquoi utiliser une pile
Pile d'appels de fonctionsEnregistrer les adresses de retour des fonctions et les variables localesLes appels de fonctions sont imbriqués, naturellement LIFO
Appariement des parenthèsesVérifier si les parenthèses dans le code sont correctement appariéesEmpiler la parenthèse gauche sur la pile, dépiler la parenthèse droite lorsqu'elle correspond au sommet de la pile
Opération d'annulationFonction d'annulation dans les éditeurs de texte et les navigateursChaque opération est empilée sur la pile, dépilée lors de l'annulation
Évaluation d'expressionsÉvaluer des expressions infixes/postfixéesLes opérandes sont empilés sur la pile, le résultat est empilé après le calcul de l'opérateur
Recherche en profondeur d'abordAlgorithme de parcours DFS pour les graphesUtiliser explicitement une pile ou la récursion (en utilisant implicitement la pile d'appels)
Autres extensions