Idee et operations
Une pile suit la regle LIFO. Les operations sont simples mais puissantes: push, pop, top. Temps O(1), espace O(n).
Invariant: top == -1 si la pile est vide.
Code minimal
#define STACK_MAX 1024
typedef struct { int data[STACK_MAX]; int top; } Stack;
void stack_init(Stack *s) { s->top = -1; }
int stack_push(Stack *s, int v) { if (s->top >= STACK_MAX - 1) return 0; s->data[++s->top] = v; return 1; }
int stack_pop(Stack *s, int *out) { if (s->top < 0) return 0; *out = s->data[s->top--]; return 1; }
Interface claire: on renvoie un booleen, les valeurs passent par out.
Application: calculette postfix
Lire chaque token. Si c'est un operateur, depiler deux valeurs et empiler le resultat. Sinon, empiler le nombre.
Demo: make demo1
Application: pile d'appels
Chaque appel de fonction empile un cadre. Recursion = pile d'appels. Trop de recursion = stack overflow.
Application: parentheses bien formees
Empiler les ouvrants, depiler sur les fermants. Une pile vide trop tot ou non vide a la fin signale une erreur.