Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C

Pile LIFO sur tableau dynamique en C

Une pile LIFO retire d’abord le dernier enregistrement ajouté. Distinguez le nombre d’éléments de la capacité et agrandissez le tampon sans perdre de données si l’allocation échoue.

Version : ISO C23; implementation support may vary

Syntaxe

/* Application-defined operations in ISO C23; not standard-library APIs. */
/* Inside main, after the application types and functions are defined. */
Stack s = { .data = NULL, .size = 0, .capacity = 0 };
Process p;
if (!push(&s, (Process){ .id = 42 }) ||
    !peek(&s, &p) ||
    !pop(&s, &p)) {
    free(s.data);
    return EXIT_FAILURE;
}
/* All three calls succeeded; p holds the record copied by pop. */
free(s.data);

Une pile LIFO suit le principe « dernier entré, premier sorti ». push ajoute un élément au sommet, peek copie l’élément du sommet sans le retirer, et pop le copie et le retire. Ce sont des fonctions de l’exemple, pas de la bibliothèque standard du C. peek et pop exigent un pointeur valide vers un objet Process distinct et accessible en écriture. Si la pile est vide, elles renvoient false sans modifier cet objet.

L’invariant est 0 <= size <= capacity : size compte les enregistrements stockés et capacity les emplacements réservés. Le sommet est à l’indice size - 1 seulement si size > 0. pop diminue size sans libérer le tampon. La valeur initiale NULL indique l’absence de tampon. La macro NULL, disponible notamment dans <stdlib.h>, se développe en une constante de pointeur nul définie par l’implémentation.

Quand la pile est pleine, push part d’un emplacement, puis double la capacité sans dépasser SIZE_MAX / sizeof *s->data. SIZE_MAX, dans <stdint.h>, est la plus grande valeur de size_t, pas la quantité de mémoire disponible. Cette limite évite les dépassements lors du calcul de la capacité et du nombre d’octets. Le résultat de realloc pour une taille non nulle est placé dans un pointeur temporaire : NULL indique un échec et la pile reste intacte. Après une réallocation réussie, n’utilisez plus les anciens pointeurs vers le tampon ou ses éléments, même si l’adresse n’a pas changé.

Si la capacité ne peut pas augmenter ou si l’allocation échoue, push renvoie false. main signale l’erreur sur stderr, libère le tampon avec free et renvoie EXIT_FAILURE de <stdlib.h> pour signaler l’échec à l’environnement hôte, sans présumer de la valeur numérique du statut.

Le littéral composé (Process){ .id = 10 } crée un objet Process sans nom ; ce n’est pas une conversion de type. Ce littéral a une durée de stockage automatique, et push stocke l’enregistrement par valeur, pas son adresse. L’exemple est conforme à ISO C23 ; cette forme de littéral existe depuis C99, mais la prise en charge du mode C23 dépend de l’implémentation.

Exemples

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

typedef struct { int id; } Process;

typedef struct {
    Process *data;
    size_t size;
    size_t capacity;
} Stack;

static bool push(Stack *s, Process value)
{
    if (s->size == s->capacity) {
        const size_t limit = SIZE_MAX / sizeof *s->data;
        if (s->capacity == limit)
            return false;

        size_t next = s->capacity == 0 ? 1
                    : s->capacity > limit / 2 ? limit
                    : s->capacity * 2;
        Process *new_data = realloc(s->data, next * sizeof *s->data);
        if (new_data == NULL)
            return false;
        s->data = new_data;
        s->capacity = next;
    }
    s->data[s->size] = value;
    ++s->size;
    return true;
}

static bool peek(const Stack *s, Process *out)
{
    if (s->size == 0)
        return false;
    *out = s->data[s->size - 1];
    return true;
}

static bool pop(Stack *s, Process *out)
{
    if (!peek(s, out))
        return false;
    --s->size;
    return true;
}

int main(void)
{
    Stack s = { .data = NULL, .size = 0, .capacity = 0 };
    if (!push(&s, (Process){ .id = 10 }) ||
        !push(&s, (Process){ .id = 20 })) {
        fputs("Cannot grow stack\n", stderr);
        free(s.data);
        return EXIT_FAILURE;
    }

    Process p;
    if (peek(&s, &p))
        printf("peek: %d\n", p.id);
    while (pop(&s, &p))
        printf("pop: %d\n", p.id);
    puts("empty");

    free(s.data);
    return EXIT_SUCCESS;
}

Résultat

peek: 20
pop: 20
pop: 10
empty

Deux ajouts font passer la capacité de 1 à 2. Après un appel réussi à `peek`, le programme affiche l’identifiant `20`. Les deux premiers appels à `pop` renvoient chacun `true` et écrivent via `out` d’abord l’enregistrement d’identifiant `20`, puis celui d’identifiant `10`. L’appel suivant à `pop` renvoie `false` parce que la pile est vide.

Leçons associées

  • C · Leçon 87 · Avancé · Version : 3

Sources