Deux piles dans un seul tableau

/* Deux piles dos a dos : A croit depuis la gauche, B depuis la droite.
   INVARIANT : na >= 0, nb >= 0, na + nb <= CAPACITE.
   La pile A occupe tab[0 .. na-1], la pile B occupe tab[C-nb .. C-1]. */
typedef struct { int tab[CAPACITE]; int na; int nb; } bipile;

bool empiler_a(bipile* p, int x) {
    if (p->na + p->nb == CAPACITE) { return false; }   /* plein : les deux */
    p->tab[p->na] = x;
    p->na = p->na + 1;
    return true;
}
bool empiler_b(bipile* p, int x) {
    if (p->na + p->nb == CAPACITE) { return false; }
    p->tab[CAPACITE - 1 - p->nb] = x;
    p->nb = p->nb + 1;
    return true;
}

La preuve de non-recouvrement tient à l'invariant $n_a+n_b\le C$. La pile A occupe les indices $0$ à $n_a-1$ ; la pile B occupe les indices $C-n_b$ à $C-1$. Ces deux intervalles sont disjoints si et seulement si $n_a-1<C-n_b$, c'est-à-dire $n_a+n_b<C+1$, c'est-à-dire $n_a+n_b\le C$ : exactement l'invariant. Or les deux fonctions ne l'augmentent que lorsqu'il est strictement inférieur à $C$, donc il est préservé.

Mesuré, avec $C=8$ : la pile A remplit à elle seule les huit cases si l'autre est vide ; et après $10,11,12$ dans A puis $90,91,92$ dans B, le tableau vaut

[10 11 12 . . 92 91 90]      na = 3, nb = 3

On lit la pile B à l'envers dans le tableau : son sommet, le dernier empilé, est en case $C-n_b=5$.

Ce que le procédé gagne. Deux piles séparées de capacité $C/2$ chacune débordent dès qu'une seule dépasse la moitié, même si l'autre est vide. Ici, les deux se partagent le tableau dynamiquement : le seul cas d'échec est celui où le total dépasse $C$, et il est inévitable. C'est un cas particulier d'une idée générale — mettre en commun une réserve plutôt que la découper d'avance —, la même qui fait préférer une allocation dynamique à un tableau statique.

La limite, à dire honnêtement : le procédé ne se généralise pas à trois piles. Un tableau n'a que deux bouts.