Table des matières

Implémentation d'une Pile en C

Stratégie utilisant un tableau

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

Création de la pile

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);
}

Deux remarques :

  • L'utilisation de malloc empêche ce programme de fonctionner avec un compilateur C++. Si vous utilisez C playground, pensez à configurer avec un compilateur C.
  • Certains compilateurs peuvent être gênés par le fait que l'on pourrait très bien écrire une déclaration comme int* truc = malloc((N+1)*sizeof(float)) dans laquelle les parties gauche et droite ne coïncide pas.
    Une solution est décrire int *truc = malloc((N+1)*sizeof(*truc)) de sorte qu'il y a forcément correspondance des deux côtés.
    On pourra donc écrire 
    int *tableau = malloc((N+1)*sizeof(*tableau));

Autres fonctions

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;
}

Utilisation typedef

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.

Fichier final

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;
}