On se contente d'une pile d'entiers.

La structure naturelle est le tableau. Mais le tableau a une taille fixe en C alors qu'une pile devrait avoir une taille variable. On pourrait créer un tableau de taille suffisamment grande pour stocker notre pile.

pile vide : [?, ?, ?, ?, ...]
empiler 15 : [15, ?, ?, ?, ...]
empiler 28 : [15, 28, ?, ?, ...]
empiler 34 : [15, 28, 34, ?, ...]
dépiler : [15, 28, ?, ?, ...] et renvoie 34

Puisque cette pile est constituée d'un tableau contenant toujours des entiers, il faut savoir où se trouve le dessus de la pile. On pourrait décider que le dernier élément du tableau contient toujours la taille de la pile.

pile vide : [?, ?, ?, ?, ..., 0]
empiler 15 : [15, ?, ?, ?, ..., 1]
empiler 28 : [15, 28, ?, ?, ..., 2]
empiler 34 : [15, 28, 34, ?, ..., 3]
dépiler : [15, 28, ?, ?, ..., 2] et renvoie 34

• il faut définir une constante N, par exmple 1000 qui fixe la taille maximale de la pile,
• définir un tableau d'entiers de taille N + 1,
• écrire 0 dans la dernière case du tableau.

Je rappelle que la variable qui résulte de la création d'un tableau de int contient l'adresse mémoire de la première case du tableau. Il s'agit d'un pointeur sur entier donc un int *.

La fonction CREER_PILE_VIDE() renvoie donc un int *.

On pourrait penser que ce ci convient

#define N 1000

int *CREER_PILE_VIDE()
{
    int tableau[N+1];
    tableau[N] = 0;
    return tableau;
}

Mais non, comme c'est expliqué ici.

On est obligé de faire ceci :

#define N 1000

int *CREER_PILE_VIDE()
{
    int *tableau = malloc((N+1)*sizeof(int));
    if (tableau == NULL)
    {
        printf("Erreur création pile.\n");
        exit(1);
    }
    tableau[N] = 0;
    return tableau;
}

Le malloc a pour effet que l'espace mémoire réservé pour le tableau n'est pas libéré à la fin de la fonction. Il faudra penser à libérer cet espace quand on libérera la pile, on ajoute donc la fonction :

void FREE_PILE(int *p)
{
    free(p);
}

Le reste est beaucoup plus simple et direct.

void EMPILER(int *p, int e)
{
    int s = p[N];
    if (s == N)
    {
        printf("Erreur : Pile pleine.\n");
        exit(1);
    }
    p[s] = e;
    p[N] = s + 1;
}

int DEPILER(int *p)
{
    int s = p[N];
    if (s == 0)
    {
        printf("Erreur : Pile vide.\n");
        exit(1);
    }
    int e = p[s-1];
    p[N] = s - 1;
    return e;
}

int EST_VIDE(int *p)
{
    if (p[N] == 0)
    {
        return 1;
    }
    return 0;
}

int EST_PLEINE(int *p)
{
    if (p[N] == N)
    {
        return 1;
    }
    return 0;
}

On constate que dans l'ensemble du programme, on utilise int* pour notre pile ce qui est lié au fait que notre pile est un tableau d'entiers. Pour rendre les choses plus claires, on peut définir une étiquette pour int* :

typedef int* Pile;

Ainsi, toutes les occurrences de int * ou int* pourront être remplacées par Pile.

Avec un exemple d'utilisation

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

#define N 1000

typedef int* Pile;

Pile CREER_PILE_VIDE()
{
    Pile p = malloc((N+1)*sizeof(*p));
    if (p == NULL)
    {
        printf("Erreur création pile.\n");
        exit(1);
    }
    p[N] = 0;
    return p;
}

void FREE_PILE(Pile p)
{
    free(p);
}

void EMPILER(Pile p, int e)
{
    int s = p[N];
    if (s == N)
    {
        printf("Erreur : Pile pleine.\n");
        exit(1);
    }
    p[s] = e;
    p[N] = s + 1;
}

int DEPILER(Pile p)
{
    int s = p[N];
    if (s == 0)
    {
        printf("Erreur : Pile vide.\n");
        exit(1);
    }
    int e = p[s-1];
    p[N] = s - 1;
    return e;
}

int EST_VIDE(Pile p)
{
    if (p[N] == 0)
    {
        return 1;
    }
    return 0;
}

int EST_PLEINE(Pile p)
{
    if (p[N] == N)
    {
        return 1;
    }
    return 0;
}

int main()
{
    Pile p = CREER_PILE_VIDE();
    EMPILER(p, 45);
    EMPILER(p, 17);
    EMPILER(p, 19);
    EMPILER(p, 50);
    int x = DEPILER(p);
    printf("%d\n", x);
    x = DEPILER(p);
    printf("%d\n", x);
    FREE_PILE(p);
    return 0;
}