Fil d'Ariane
Mis à jour le vendredi 10 mars 2017
  • 40 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

Ce cours existe en livre papier.

Ce cours existe en eBook.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Les piles et les files

Connectez-vous ou inscrivez-vous pour bénéficier de toutes les fonctionnalités de ce cours !

Nous avons découvert avec les listes chaînées un nouveau moyen plus souple que les tableaux pour stocker des données. Ces listes sont particulièrement flexibles car on peut insérer et supprimer des données à n'importe quel endroit, à n'importe quel moment.

Les piles et les files que nous allons découvrir ici sont deux variantes un peu particulières des listes chaînées. Elles permettent de contrôler la manière dont sont ajoutés les nouveaux éléments. Cette fois, on ne va plus insérer de nouveaux éléments au milieu de la liste mais seulement au début ou à la fin.

Les piles et les files sont très utiles pour des programmes qui doivent traiter des données qui arrivent au fur et à mesure. Nous allons voir en détails leur fonctionnement dans ce chapitre.

Les piles et les files sont très similaires, mais révèlent néanmoins une subtile différence que vous allez rapidement reconnaître. Nous allons dans un premier temps découvrir les piles qui vont d'ailleurs beaucoup vous rappeler les listes chaînées, à quelques mots de vocabulaire près.

Globalement, ce chapitre sera simple pour vous si vous avez compris le fonctionnement des listes chaînées. Si ce n'est pas le cas, retournez d'abord au chapitre précédent car nous allons en avoir besoin.

Les piles

Imaginez une pile de pièces (fig. suivante). Vous pouvez ajouter des pièces une à une en haut de la pile, mais aussi en enlever depuis le haut de la pile. Il est en revanche impossible d'enlever une pièce depuis le bas de la pile. Si vous voulez essayer, bon courage !

Une pile de pièces

Fonctionnement des piles

Le principe des piles en programmation est de stocker des données au fur et à mesure les unes au-dessus des autres pour pouvoir les récupérer plus tard. Par exemple, imaginons une pile de nombres entiers de typeint(fig. suivante). Si j'ajoute un élément (on parle d'empilage), il sera placé au-dessus, comme dans Tetris (fig. suivante).

Une pile de int
Empilage

Le plus intéressant est sans conteste l'opération qui consiste à extraire les nombres de la pile. On parle de dépilage. On récupère les données une à une, en commençant par la dernière qui vient d'être posée tout en haut de la pile (fig. suivante). On enlève les données au fur et à mesure, jusqu'à la dernière tout en bas de la pile.

Dépilage

On dit que c'est un algorithme LIFO, ce qui signifie « Last In First Out ». Traduction : « Le dernier élément qui a été ajouté est le premier à sortir ».

Les éléments de la pile sont reliés entre eux à la manière d'une liste chaînée. Ils possèdent un pointeur vers l'élément suivant et ne sont donc pas forcément placés côte à côte en mémoire. Le dernier élément (tout en bas de la pile) doit pointer versNULLpour indiquer qu'on a… touché le fond (fig. suivante).

Les éléments sont reliés entre eux et le dernier pointe vers NULL

À quoi est-ce que tout cela peut bien servir, concrètement ?

Il y a des programmes où vous avez besoin de stocker des données temporairement pour les ressortir dans un ordre précis : le dernier élément que vous avez stocké doit être le premier à ressortir.

Pour vous donner un exemple concret, votre système d'exploitation utilise ce type d'algorithme pour retenir l'ordre dans lequel les fonctions ont été appelées. Imaginez un exemple :

  1. votre programme commence par la fonctionmain(comme toujours) ;

  2. vous y appelez la fonctionjouer;

  3. cette fonctionjouerfait appel à son tour à la fonctioncharger;

  4. une fois que la fonctionchargerest terminée, on retourne à la fonctionjouer;

  5. une fois que la fonctionjouerest terminée, on retourne aumain;

  6. enfin, une fois lemainterminé, il n'y a plus de fonction à appeler, le programme s'achève.

Pour « retenir » l'ordre dans lequel les fonctions ont été appelées, votre ordinateur crée une pile de ces fonctions au fur et à mesure (fig. suivante).

La pile d'appel des fonctions au fur et à mesure du programme

Voilà un exemple concret d'utilisation des piles. Grâce à cette technique, votre ordinateur sait à quelle fonction il doit retourner. Il peut empiler 100 fonctions d'affilée s'il le faut, il retrouvera toujours lemainen bas !

Création d'un système de pile

Maintenant que nous connaissons le principe de fonctionnement des piles, essayons d'en construire une. Comme pour les listes chaînées, il n'existe pas de système de pile intégré au langage C. Il faut donc le créer nous-mêmes.

Chaque élément de la pile aura une structure identique à celle d'une liste chaînée :

typedef struct Element Element;
struct Element
{
    int nombre;
    Element *suivant;
};

La structure de contrôle contiendra l'adresse du premier élément de la pile, celui qui se trouve tout en haut :

typedef struct Pile Pile;
struct Pile
{
    Element *premier;
};

Nous aurons besoin en tout et pour tout des fonctions suivantes :

  • empilage d'un élément ;

  • dépilage d'un élément.

Vous noterez que, contrairement aux listes chaînées, on ne parle pas d'ajout ni de suppression. On parle d'empilage et de dépilage car ces opérations sont limitées à un élément précis, comme on l'a vu. Ainsi, on ne peut ajouter et retirer un élément qu'en haut de la pile.

On pourra aussi écrire une fonction d'affichage de la pile, pratique pour vérifier si notre programme se comporte correctement.

Allons-y !

Empilage

Notre fonctionempilerdoit prendre en paramètre la structure de contrôle de la pile (de typePile) ainsi que le nouveau nombre à stocker.
Je vous rappelle que nous stockons ici desint, mais rien ne vous empêche d'adapter ces exemples avec un autre type de données. On peut stocker n'importe quoi : desdouble, deschar, des chaînes, des tableaux ou même d'autres structures !

void empiler(Pile *pile, int nvNombre)
{
    Element *nouveau = malloc(sizeof(*nouveau));
    if (pile == NULL || nouveau == NULL)
    {
        exit(EXIT_FAILURE);
    }

    nouveau->nombre = nvNombre;
    nouveau->suivant = pile->premier;
    pile->premier = nouveau;
}

L'ajout se fait en début de pile car, comme on l'a vu, il est impossible de le faire au milieu d'une pile. C'est le principe même de son fonctionnement, on ajoute toujours par le haut.
De ce fait, contrairement aux listes chaînées, on ne doit pas créer de fonction pour insérer un élément au milieu de la pile. Seule la fonctionempilerpermet d'ajouter un élément.

Dépilage

Le rôle de la fonction de dépilage est de supprimer l'élément tout en haut de la pile, ça, vous vous en doutiez. Mais elle doit aussi retourner l'élément qu'elle dépile, c'est-à-dire dans notre cas le nombre qui était stocké en haut de la pile.

C'est comme cela que l'on accède aux éléments d'une pile : en les enlevant un à un. On ne parcourt pas la pile pour aller y chercher le second ou le troisième élément. On demande toujours à récupérer le premier.

Notre fonctiondepilerva donc retourner unintcorrespondant au nombre qui se trouvait en tête de pile :

int depiler(Pile *pile)
{
    if (pile == NULL)
    {
        exit(EXIT_FAILURE);
    }

    int nombreDepile = 0;
    Element *elementDepile = pile->premier;

    if (pile != NULL && pile->premier != NULL)
    {
        nombreDepile = elementDepile->nombre;
        pile->premier = elementDepile->suivant;
        free(elementDepile);
    }

    return nombreDepile;
}

On récupère le nombre en tête de pile pour le renvoyer à la fin de la fonction. On modifie l'adresse du premier élément de la pile, puisque celui-ci change. Enfin, bien entendu, on supprime l'ancienne tête de pile grâce àfree.

Affichage de la pile

Bien que cette fonction ne soit pas indispensable (les fonctionsempileretdepilersuffisent à gérer une pile !), elle va nous être utile pour tester le fonctionnement de notre pile et surtout pour « visualiser » le résultat.

void afficherPile(Pile *pile)
{
    if (pile == NULL)
    {
        exit(EXIT_FAILURE);
    }
    Element *actuel = pile->premier;

    while (actuel != NULL)
    {
        printf("%d\n", actuel->nombre);
        actuel = actuel->suivant;
    }

    printf("\n");
}

Cette fonction étant ridiculement simple, elle ne nécessite aucune explication (et toc !).

En revanche, c'est le moment de faire unmainpour tester le comportement de notre pile :

int main()
{
    Pile *maPile = initialiser();

    empiler(maPile, 4);
    empiler(maPile, 8);
    empiler(maPile, 15);
    empiler(maPile, 16);
    empiler(maPile, 23);
    empiler(maPile, 42);

    printf("\nEtat de la pile :\n");
    afficherPile(maPile);

    printf("Je depile %d\n", depiler(maPile));
    printf("Je depile %d\n", depiler(maPile));

    printf("\nEtat de la pile :\n");
    afficherPile(maPile);

    return 0;
}

On affiche l'état de la pile après plusieurs empilages et une autre fois après quelques dépilages. On affiche aussi le nombre qui est dépilé à chaque fois que l'on dépile. Le résultat dans la console est le suivant :

Etat de la pile :
42
23
16
15
8
4

Je depile 42
Je depile 23

Etat de la pile :
16
15
8
4

Vérifiez que vous voyez bien ce qui se passe dans ce programme. Si vous comprenez cela, vous avez compris le fonctionnement des piles !

Vous pouvez télécharger le projet complet des piles si vous le désirez.

Télécharger le projet complet des piles

Les files

Les files ressemblent assez aux piles, si ce n'est qu'elles fonctionnent dans le sens inverse !

Fonctionnement des files

Dans ce système, les éléments s'entassent les uns à la suite des autres. Le premier qu'on fait sortir de la file est le premier à être arrivé. On parle ici d'algorithme FIFO (First In First Out), c'est-à-dire « Le premier qui arrive est le premier à sortir ».

Il est facile de faire le parallèle avec la vie courante. Quand vous allez prendre un billet de cinéma, vous faites la queue au guichet (fig. suivante). À moins d'être le frère du guichetier, vous allez devoir faire la queue comme tout le monde et attendre derrière. C'est le premier arrivé qui sera le premier servi.

Une file d'attente. Le premier arrivé est le premier servi

En programmation, les files sont utiles pour mettre en attente des informations dans l'ordre dans lequel elles sont arrivées. Par exemple, dans un logiciel de chat (type messagerie instantanée), si vous recevez trois messages à peu de temps d'intervalle, vous les enfilez les uns à la suite des autres en mémoire. Vous vous occupez alors du premier message arrivé pour l'afficher à l'écran, puis vous passez au second, et ainsi de suite.

Les événements que vous envoie la bibliothèque SDL que nous avons étudiée sont eux aussi stockés dans une file. Si vous bougez la souris, un événement sera généré pour chaque pixel dont s'est déplacé le curseur de la souris. La SDL les stocke dans une file puis vous les envoie un à un à chaque fois que vous faites appel àSDL_PollEvent(ou àSDL_WaitEvent: oui, c'est bien ! Je vois que ça suit au fond de la classe. ;) ).

En C, une file est une liste chaînée où chaque élément pointe vers le suivant, tout comme les piles. Le dernier élément de la file pointe versNULL(fig. suivante).

Représentation d'une file

Création d'un système de file

Le système de file va ressembler à peu de choses près aux piles. Il y a seulement quelques petites subtilités étant donné que les éléments sortent de la file dans un autre sens, mais rien d'insurmontable si vous avez compris les piles.

Nous allons créer une structureElementet une structure de contrôleFile:

typedef struct Element Element;
struct Element
{
    int nombre;
    Element *suivant;
};

typedef struct File File;
struct File
{
    Element *premier;
};

Comme pour les piles, chaque élément de la file sera de typeElement. À l'aide du pointeurpremier, nous disposerons toujours du premier élément et nous pourrons remonter jusqu'au dernier.

Enfilage

La fonction qui ajoute un élément à la file est appelée fonction « d'enfilage ». Il y a deux cas à gérer :

  • soit la file est vide, dans ce cas on doit juste créer la file en faisant pointerpremiervers le nouvel élément créé ;

  • soit la file n'est pas vide, dans ce cas il faut parcourir toute la file en partant du premier élément jusqu'à arriver au dernier. On rajoutera notre nouvel élément après le dernier.

Voici comment on peut faire dans la pratique :

void enfiler(File *file, int nvNombre)
{
    Element *nouveau = malloc(sizeof(*nouveau));
    if (file == NULL || nouveau == NULL)
    {
        exit(EXIT_FAILURE);
    }

    nouveau->nombre = nvNombre;
    nouveau->suivant = NULL;

    if (file->premier != NULL) /* La file n'est pas vide */
    {
        /* On se positionne à la fin de la file */
        Element *elementActuel = file->premier;
        while (elementActuel->suivant != NULL)
        {
            elementActuel = elementActuel->suivant;
        }
        elementActuel->suivant = nouveau;
    }
    else /* La file est vide, notre élément est le premier */
    {
        file->premier = nouveau;
    }
}

Vous voyez dans ce code le traitement des deux cas possibles, chacun devant être géré à part. La différence par rapport aux piles, qui rajoute une petite touche de difficulté, est qu'il faut se placer à la fin de la file pour ajouter le nouvel élément. Mais bon, un petitwhileet le tour est joué, comme vous pouvez le constater. :-)

Défilage

Le défilage ressemble étrangement au dépilage. Étant donné qu'on possède un pointeur vers le premier élément de la file, il nous suffit de l'enlever et de renvoyer sa valeur.

int defiler(File *file)
{
    if (file == NULL)
    {
        exit(EXIT_FAILURE);
    }

    int nombreDefile = 0;

    /* On vérifie s'il y a quelque chose à défiler */
    if (file->premier != NULL)
    {
        Element *elementDefile = file->premier;

        nombreDefile = elementDefile->nombre;
        file->premier = elementDefile->suivant;
        free(elementDefile);
    }

    return nombreDefile;
}

À vous de jouer !

Il resterait à écrire une fonctionafficherFile, comme on l'avait fait pour les piles. Cela vous permettrait de vérifier si votre file se comporte correctement.

Réalisez ensuite unmainpour faire tourner votre programme. Vous devriez pouvoir obtenir un rendu similaire à ceci :

Etat de la file :
4 8 15 16 23 42

Je defile 4
Je defile 8

Etat de la file :
15 16 23 42

À terme, vous devriez pouvoir créer votre propre bibliothèque de files, avec des fichiersfile.hetfile.cpar exemple.

Je vous propose de télécharger le projet complet de gestion des files, si vous le désirez. Il inclut la fonctionafficherFile.

Télécharger le projet complet des files

En résumé

  • Les piles et les files permettent d'organiser en mémoire des données qui arrivent au fur et à mesure.

  • Elles utilisent un système de liste chaînée pour assembler les éléments.

  • Dans le cas des piles, les données s'ajoutent les unes au-dessus des autres. Lorsqu'on extrait une donnée, on récupère la dernière qui vient d'être ajoutée (la plus récente). On parle d'algorithme LIFO (Last In First Out).

  • Dans le cas des files, les données s'ajoutent les unes à la suite des autres. On extrait la première donnée à avoir été ajoutée dans la file (la plus ancienne). On parle d'algorithme FIFO (First In First Out).

Exemple de certificat de réussite
Exemple de certificat de réussite