CodeUtility
Faciliter la vie des développeurs !
Structures de données en C/C++

La structure de données pile (stack) en C et C++

Dans cette leçon, vous allez implémenter les opérations d'une pile, selon la règle dernier entré, premier sorti, avec un tableau fixe en C et std::stack en C++.

Introduction

La pile (stack) ne permet d'agir qu'au sommet : push place un nouvel élément au sommet, pop retire l'élément du sommet, et peek consulte le sommet sans le retirer. La pile suit la règle dernier entré, premier sorti (LIFO), comme une pile de livres.

Points importants

  • Définissez les conditions qui doivent toujours être vraies (invariants) avant d'écrire les opérations.
  • Traitez les cas de structure vide, pleine et d'échec d'allocation mémoire.
  • Évaluez ensemble la complexité et la gestion mémoire de chaque opération.

Voir comment ça marche

Faites push et pop pour voir que le dernier élément entré est toujours le premier à sortir.

Exemples de code C et C++

C
Exécuter →
main.c
#include <stdio.h>

typedef struct {
    int data[8];
    int size;
} Stack;

int push(Stack *stack, int value) {
    if (stack->size == 8) return 0;
    stack->data[stack->size++] = value;
    return 1;
}

int pop(Stack *stack, int *value) {
    if (stack->size == 0) return 0;
    *value = stack->data[--stack->size];
    return 1;
}

int main(void) {
    Stack stack = {{0}, 0};
    int value;
    push(&stack, 10);
    push(&stack, 20);
    pop(&stack, &value);
    printf("%d\n", value);
}
Résultat de l’exécution
20
C++
Exécuter →
main.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> values;
    values.push(10);
    values.push(20);
    std::cout << values.top() << '\n';
    values.pop();
}
Résultat de l’exécution
20

Comparaison entre C et C++

La version C utilise un tableau fixe de 8 éléments, elle doit donc vérifier que la pile n'est pas pleine lors d'un push (débordement de pile) et pas vide lors d'un pop. En C++, std::stack gère la capacité au moyen du conteneur sous-jacent et propose les mêmes opérations push, pop et top selon la règle LIFO.

C

Les données (struct) et les opérations sont séparées, et la mémoire est allouée et libérée à la main.

C++

Les classes et les conteneurs protègent la cohérence des données et gèrent eux-mêmes leurs ressources.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

  • Ajoutez des tests pour l'état vide et pour le moment où la capacité maximale est atteinte.
  • Écrivez la libération de la mémoire et vérifiez qu'il n'y a pas de fuite.
  • Comparez la complexité avec celle du conteneur équivalent de la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis