1. Le type abstrait File (Queue ou FIFO)

Dans cette définition basique du TAD file, on ne peut accéder qu'à la queue de la file pour enfiler un nouvel élément, et à la tête de la file pour défiler un élément. A l'inverse, il n'est pas possible d'accéder à un élément à l'intérieur de la file.

Les opérations du TAD File sont toutefois parfois complétées :

• Afficher (print) : affiche tous les éléments présents dans la filer
• Compter (count): retourne le nombre d'éléments présents dans la file
• etc.

La fin de cette fiche discute deux implémentations du type abstrait File en C. La seconde, qui s'appuie sur une liste circulaire avec pointeur sur la queue sera "l'implémentation de référence" pour ce module d'informarique : à bien connaître !

2. [Appartée] Implémentation au moyen d'une liste chaînée dynamique avec double pointeur tête-queue

Il serait possible de réaliser le TAD file au moyen d'une simple liste chaînée dynamique :

• Enfiler pourrait être ajouter en queue de la liste.
• Défiler pourrait être supprimer la tête de la liste.
• (ou l'inverse d'ailleurs)

Le problème de cette approche est qu'alors enfiler nécessite d'accéder au dernier élément, en queue de la liste. Mais pour accéder à la queue, il faut parcourir la liste ! Le coût du parcours est alors en O(n), ce qui est prohibitif puisque, avec le TAD File, on attend que l'ajout d'un élément en queue soit à coût constant.

Une ruse consiste à se débrouiller pour conserver un pointeur sur le maillon de queue en plus du pointeur sur le maillon de tête. On réalise ainsi une structure de donnée nommée liste chaînée dynamique avec double pointeur tête-queue

Implémentation du TAD file au moyen d'une liste chaînée dynamique avec double pointeur tête - queue.
Dans cet exemple, les éléments sont de type double

En C, le type fifo_t n'est alors plus un simple pointeur sur maillon, mais un type structuré contenant deux pointeurs. La déclaration du type s'écrit alors comme suit dans le fichier header fifo.h du module fifo :

          // extrait du fichier fifo.h pour l'implantation du TAD File au moyen
          // d'une liste chaînée dynamique avec deux pointeurs sur la tête et sur la queue
          #ifndef FIFO_H_
          #define FIFO_H_

          #include "element.h"

          // 1. Définition du type maillon (fifolink_t)
          // C'est comme pour les listes chaînées !
          typedef struct _link {
            element_t val; /* un élément de la liste*/
            struct _link *next; /* l'adresse du maillon suivant */
          } fifolink_t;

          // Par contre, dans ce cas, une file est une variable structurée contenant DEUX pointeurs
          // Le type fifo_t est donc :
          typedef struct {
            fifolink_t * head;  // pointeur sur le maillon en tête de liste
            fifolink_t * tail;  // pointeur sur le maillon en queue de liste
          } fifo_t;

          ...

          #endif
          

Voici alors un exemple d'évolution d'une variable file de type fifo_t au fur et à mesure de son usage :

Exemple d'usage d'une file implantée par liste chaînée dynamique avec double pointeur tête - queue.

Pour finir, réfléchissons, par exemple, au code de la fonction fifo_dequeue() qui soit retourner l'élément en tête de file et supprimer la tête.

Le prototype que nous choisissons pour cette fonction est :

            // Enlève l'élément en tête de la file, et retourne cet élément
            // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
            element_t fifo_dequeue(fifo_t * p_queue) ;
          

Notez que, comme cette fonction doit "retourner" à la fois l'élément qui était en tête de file et la file modifiée, on a choisit pour ce prototype de passer la file par pointeur et de retourner (au sens de return) l'élément qui était en tête.

                  // Enlève l'élément en tête de la file, et retourne cet élément
                  // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
                  element_t fifo_dequeue(fifo_t * p_queue) {
                    element_t e = p_queue->head->val;
                    p_queue->head = p_queue->head->next;
                    return e;
                  }
              

                  // Enlève l'élément en tête de la file, et retourne cet élément
                  // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
                  element_t fifo_dequeue(fifo_t * p_queue) {
                    free(p_queue->head);
                    p_queue->head = p_queue->head->next;
                    return p_queue->head->val;
                  }
                

                   // Enlève l'élément en tête de la file, et retourne cet élément
                   // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
                   element_t fifo_dequeue(fifo_t * p_queue) {
                     element_t e = p_queue->head->val;
                     fifolink_t * newhead = p_queue->head->next;
                     free(p_queue->head);
                     p_queue->head = newhead;
                     return e;
                   }
                 

                   // Enlève l'élément en tête de la file, et retourne cet élément
                   // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
                   element_t fifo_dequeue(fifo_t * p_queue) {
                     assert(! fifo_is_empty(*p_queue));

                     element_t e = p_queue->head->val;
                     fifolink_t * newhead = p_queue->head->next;
                     free(p_queue->head);
                     p_queue->head = newhead;
                     if(newhead == NULL) {
                       p_queue->tail = NULL;
                     }
                     return e;
                   }
                 

3. Implémentation au moyen d'une liste chaînée circulaire avec pointeur sur la queue

L'implémentation des files qui précède est couremment utilisée, mais, pour garantir qu'enfiler et défiler sont à coût constant, on peut faire encore plus rusé au moyen d'une structure de donnée liste chaînée circulaire avec pointeur sur la queue.

3.1 Bases de l'implémentation

Cette structure de données :

• Permet bien d'accéder à la queue en O(1). Ainsi, l'ajout d'un élément en queue est réalisable à coût constant.
• Mais permet aussi d'accéder à la tête en O(1). Il suffit en effet d'accéder au maillon en queue (immédiat), puis au maillon "suivant" la queue (immédiat grâce au pointeur circulaire)... qui est la tête ! Ainsi, la suppression d'un élément en tête est elle aussi réalisable à coût constant.

Ainsi, tout en utisant cette fois-ci un unique pointeur pour manipuler la structure de données, une liste circulaire avec pointeur sur la queue permet d'implanter le TAD File en garantissant que les opération enfilage (ajout en queue de la liste) et défilage (suppression en tête de la liste) sont bien à coût constant.

Pour finir cette introduction, voyons comment une variable file évolue lorsqu'on enfile / défile quelques éléments.

Evolution d'une file implantée par liste circulaire avec pointeur sur la queue. Ici, la file contient des éléments de type double.

3.2 Déclaration du type C fifo_t dans le fichier fifo.h

Avec cette implémentation, une variable C permettant de manipuler une file est un simple pointeur sur le maillon de queue. Le type fifo_t est donc déclaré tout simplement comme on avait déclaré le type list_t pour les listes dynamiques :

        // fichier fifo.h pour l'implantation du TAD file au moyen d'une liste chaînée dynamique
        #ifndef FIFO_H_
        #define FIFO_H_

        #include "element.h" // on suppose que le type element_t est déclaré dans ce fichier

        // 1. le type fifo_t est défini comme "pointeur sur maillon"
        typedef struct _fifolink {
          element_t val; /* un élément de la liste*/
          struct _fifolink *next; /* l'adresse du maillon suivant */
        } * fifo_t;

        ...

        #endif
        

          #include "fifo.h"
          int main() {
            fifo_t file = fifo_new();

            ...
            // ajout d'éléments dans la file, gérée comme une liste circulaire
            ...

            list_print(file);

            return 0;
          }
          

3.3 API, fichier fifo.h

L'API que nous choissons pour notre implémentation de référence des files par liste chaînée circulaire est très proche de celle que nous avions retenue pour les piles.

Notez que, comme pour les piles, le contrat des fonctions de défilage s'appuient sur la précondition "le file n'est pas vide". Notez également le prototype de la fonction fifo_dequeue(), qui a recours a un passage par adresse.

        // fichier fifo.h pour l'implantation du TAD File au moyen d'une liste chaînée circulaire
        #ifndef FIFO_H_
        #define FIFO_H_

        #include "element.h" // on suppose que le type element_t est déclaré dans ce fichier

        // 1. le type fifo_t est défini comme "pointeur sur maillon"
        typedef struct _fifolink {
          element_t val; /* un élément de la liste*/
          struct _fifolink *next; /* l'adresse du maillon suivant */
        } * fifo_t;

        // 2. prototypes des fonctions de l'API du TAD File

        // Crée et retourne un file vide
        fifo_t fifo_new();

        // Détruit la file et retourne une file vide
        fifo_t fifo_delete(fifo_t queue);

        // Retourne 1 si la file  queue   est vide, 0 sinon
        int fifo_is_empty(fifo_t queue);

        // Ajoute l'élément e à la file  queue  et retourne la nouvelle file
        // Retourne NULL en cas d'erreur
        fifo_t fifo_enqueue(element_t e, fifo_t queue);

        // Retourne l'élément en tête de file (sans l'enlever de la file)
        // PRECONDITION : la file  queue  ne doit pas être vide
        element_t fifo_peek(fifo_t queue);

        // Enlève l'élément en tête de la file, et retourne cet élément
        // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
        element_t fifo_dequeue(fifo_t * p_queue);
            // Remarque sur le prototype de fifo_dequeue() :
            // Cette fonction doit "retourner" 2 choses :
            //  - l'élément qui était en tête
            //  - et la file modifiée, dont on enlevée l'ancienne tête
            // Il faut donc, en C, utiliser un passage par adresse pour l'une
            // de ces deux valeurs (ici : la file)


        // FONCTION optionnelle : affiche tous les éléments de la file, dans l'ordre
        void fifo_print(fifo_t queue);

        // FONCTION optionnelle : compte le nombre d'éléments dans la file
        int fifo_count(fifo_t queue);

        #endif
        

3.4. Opération enfilage et fonction fifo_enqueue()

Nous allons progressivement construire la fonction fifo_enqueue() en considérant d'abord le cas général, puis quelques cas particuliers. La version finale de la fonction vous est ensuite donnée.

3.4.1 fifo_enqueue() : cas général "file contenant déjà quelques éléments"

Pour réfléchir au cas général, on suppose qu'on manipule une file de double, et que la file contient déjà quelques éléments - par exemple 2 éléments :

Etat initial de la file avant l'appel à fifo_enqueue().

On veut enfiler un nouvel élément en appelant fifo_enqueue(), par exemple l'élement 8.6, en écrivant dans le main, ligne 9 :

        // main(), extrait
        #include "fifo.h"

        int main(){
          fifo_t uneFile = fifo_new();
          queue = fifo_enqueue(3.6, uneFile);
          queue = fifo_enqueue(5.4, uneFile);

          queue = fifo_enqueue(8.6, uneFile);
          ...
        }
        

L'état final auquel nous voulons arriver après l'appel à fifo_enqueue() est alors :

Etat final voulu après l'appel à fifo_enqueue().

Pour enfiler un nouvel élément, il faut dans la fonction fifo_enqueue() :

1. Allouer un maillon pour stocker l'élément enfilé. L'allocation doit bien sûr être dynamique, avec calloc(), puisque le maillon doit rester alloué après la fin de la fonction. Ce nouveau maillon, ci-dessous pointé par p est appelé à devenir la nouvelle queue de la file :

   

2. Faire pointer le champ next du nouveau maillon sur la tête de la file, pour assurer la circularité. C'est à dire c'est à dire affecter à p->next l'adresse stockée dans file->next :

   

3. Refaire le chaînage : faire que l'ancien dernier maillon pointe le maillon qui vient d'être créé (la nouvelle queue), c'est à dire mettre à jour la valeur de file->next :

   

4. Retourner l'adresse du nouveau maillon de queue de la file, c'est à dire la valeur du pointeur p, pour que la variable maFile soit mise à jour dans le main :

   

Traduit en langage C, cet algorithme s'écrit ainsi (attention : cette version n'est PAS la version finale correcte !) :

        // fichier fifo.c, extrait

        // ATTENTION : cet algorithme n'est PAS la version finale
        fifo_t fifo_enqueue(element_t e, fifo_t q){
          // étape 1 : Allouer dynamiquement un maillon et stocker l'élément dans le maillon
            fifo_t p = calloc(1, sizeof(*p));
            p->val = e;
          // étape 2 : Faire pointer le champ next du nouveau maillon sur la tête de la file
            p->next = q->next ; // q->next contient bien l'adresse de la tête de file
          // étape 3 : Refaire le chaînage
            q->next = p ; // l'ancien dernier maillon pointe le nouveau dernier maillon
          // étape 4 : retourner l'adresse du nouveau dernier maillon
            return p;
        }
        

3.4.2 fifo_enqueue() : cas particulier "file à 1 élément" et "file vide"

Maintenant que nous avons géré le cas général d'une "file contenant déjà quelques éléments", voyons comment notre algorithme résiste aux cas particuliers :

• enfiler un élément dans file à 1 unique élément
• enfiler un élément dans file vide

            fifo_t fifo_enqueue(element_t e, fifo_t q){
              fifo_t p = calloc(1, sizeof(*p));
              p->val = e;
              p->next = q->next ;
              q->next = p ;
              return p;
            }
            

              int main() {
                fifo_t f = fifo_new();
                f = fifo_enqueue(3.6, f); // ajout d'un premier élément. On suppose que ca marche

                f = fifo_enqueue(2.0, f); // ajout d'un second élément
                ...
              }
              

            fifo_t fifo_enqueue(element_t e, fifo_t q){
              fifo_t p = calloc(1, sizeof(*p));
              p->val = e;
              p->next = q->next ;
              q->next = p ;
              return p;
            }
            

            int main() {
              fifo_t f = fifo_new();
              f = fifo_enqueue(2.0, f);
              ...
            }
            

3.4.3 Version finale de la fonction fifo_enqueue()

Puisque vous avez bien suivi, voici la version finale de la fonction fifo_enqueue() lorsque la file est réalisée par une liste cicrulaire avec pointeur sur la queue.

Tous les cas particuliers sont gérés, et on traite également le cas où calloc() échoue. A retenir !

        // fichier fifo.c, extrait
        // Version finale de la fonction fifo_enqueue() avec la structure de donnée liste chaînée circulaire

        // Ajoute l'élément e à la file  queue  et retourne la nouvelle file
        // Retourne NULL en cas d'erreur
        fifo_t fifo_enqueue(element_t e, fifo_t q){
          fifo_t p = calloc(1, sizeof(*p));
          if(p == NULL) {
            return NULL ;
          }
          p->val = e;

          // cas particulier "file vide"
          if(fifo_is_empty(q)) {
            p->next = p ; // circularité : le nouveau (unique) maillon pointe sur lui-même
            return p;
          }

          // cas général
          p->next = q->next ; // q->next contient bien l'adresse de la tête de file
          q->next = p ;       // l'ancien dernier maillon pointe le nouveau dernier maillon
          return p;
        }
        

3.5. Fonction d'affichage de tous les éléments de la file

On s'intéresse maintenant à la fonction d'affichage void fifo_print(fifo_t q); qui affiche dans l'ordre (depuis la tête jusqu'à la queue) les éléments d'une file.

Rappelons que cette fonction est optionnelle. Une vision rigoriste du TAD file interdirait en effet d'accéder à d'autres éléments que la tête de file - et donc l'affichage des éléments. Ne serait-ce que pour debugger, il est toutefois conseillé de munir ses files d'une telle fonction...

Pour écrire notre fonction, on supposera que, dans le module element.h / element.c, il existe une fonction void element_print(element_t e); qui affiche un élément.

A vous de trouver la bonne version de fifo_print() dans le QCM qui suit !

                void fifo_print(fifo_t q) {
                  fifo_t p = q;
                  // la condition d'arrêt est "p pointe le dernier maillon"
                  while(p != q) {
                    element_print(p->val);
                    printf(" ; "); // pour séparer l'affichage des elts
                    p = p->next;
                  }
                  printf("\n"); // pour terminer par un retour chariot
                }
            

                  void fifo_print(fifo_t q) {
                    fifo_t p = q->next; // on commence le maillon de TETE, or q pointe la QUEUE
                    // la condition d'arrêt est "p pointe sur le le dernier maillon"
                    while(p != q) {
                      element_print(p->val);
                      printf(" ; "); // pour séparer l'affichage des elts
                      p = p->next;
                    }
                    printf("\n"); // pour terminer par un retour chariot
                  }
              

                   void fifo_print(fifo_t q) {
                     fifo_t p = q->next; // on commence au PREMIER maillon
                     while (p != q) {
                       element_print(p->val);
                       printf(" ; "); // pour séparer l'affichage des elts
                       p = p->next;
                     } ;
                     // affichage du maillon de queue
                     element_print(p->val);
                     printf(" ; ");
                     printf("\n"); // pour terminer par un retour chariot
                   }
               

                   void fifo_print(fifo_t q) {
                     if(fifo_is_empty(q)) {
                       printf("The queue is empty\n");
                       return ; // arrêt de la fonction dans la cas particulier file vide
                     }
                     fifo_t p = q->next; // on commencera la boucle au PREMIER maillon
                     while (p != q) {
                       element_print(p->val);
                       printf(" ; "); // pour séparer l'affichage des elts
                       p = p->next;
                     } ;
                     // affichage du maillon de queue
                     element_print(p->val);
                     printf(" ; ");
                     printf("\n"); // pour terminer par un retour chariot
                   }
               

                    void fifo_print(fifo_t q) {
                      if(fifo_is_empty(q)) {
                        printf("The queue is empty\n");
                        return ;
                      }
                      fifo_t p = q->next; // on commence au PREMIER maillon
                      do {
                        element_print(p->val);
                        printf(" ; "); // pour séparer l'affichage des elts
                        p = p->next;
                      } while(p != q->next); // la condition d'arrêt est "on retrouve le dernier maillon"
                      printf("\n"); // pour terminer proprement par un retour chariot
                    }
                

3.6. Opération de défilage

Pour finir, on s'intéresse à l'algorithme de l'opération de défilage. Attention : on ne donnera pas le code C de la fonction fifo_dequeue() ! A vous de l'écrire en TD et TP !

Rappelons le contrat voulu pour cette fonction :

        // fichier fifo.h - extrait
        ...

        // Enlève l'élément en tête de la file, et retourne cet élément
        // PRECONDITION : la file pointée par  p_queue  ne doit pas être vide
        element_t fifo_dequeue(fifo_t * p_queue);
            // Remarque sur le prototype de fifo_dequeue() :
            // Cette fonction doit "retourner" 2 choses :
            //  - l'élément qui était en tête
            //  - et la file modifiée, dont on enlevée l'ancienne tête
            // Il faut donc, en C, utiliser un passage par adresse pour l'une
            // de ces deux valeurs (ici : la file)
        ...
        

3.6.1 Cas général "défiler une file contenant déjà quelques éléments"

Pour réfléchir au cas général de la fonction de défilage element_t fifo_dequeue(fifo_t * p_queue), on suppose qu'on manipule une file contenant quelques éléments - par exemple 3 éléments :

Etat initial de la file avant l'appel à fifo_dequeue().

On veut défiler l'élément de tête en appelant fifo_dequeue(), c'est à dire détruire le maillon contenant 3.6 et retourner 3.6.

Dans le main, on écrirait donc, ligne 11 :

        // main(), extrait
        #include "fifo.h"

        int main(){
          fifo_t queue = fifo_new();
          queue = fifo_enqueue(3.6, queue);
          queue = fifo_enqueue(5.4, queue);
          queue = fifo_enqueue(8,6, queue);

          // notez l'opérateur d'adresse & :
          // en conformité avec le prototype de fifo_dequeue(), qui a prend un pointeur-sur-file en paramètre
          // on passe l'adresse de la file à la fonction
          element_t tete = fifo_dequeue(&queue);
          ...
        }
        

L'état final auquel nous voulons arriver après l'appel à fifo_dequeue() est :

Etat final voulu après l'appel à fifo_dequeue().

Pour défiler l'élément de tête, il faut dans le code de la fonction element_t fifo_dequeue(fifo_t * p_queue) :

1. Mettre de côté la valeur de l'élément contenu dans le maillon de tête, pour pouvoir le retourner à la fin de la fonction. On rappelle que, dans l'API du module, la fonction element_t fifo_peek(fifo_t queue) retourne l'élément de tête (sans l'enlever). Comme p_queue pointe la variable file, on écrira :
   element_t elt_tete = fifo_peek(*p_queue);
   

   

2. Mettre de côté l'adresse du maillon de tête dans un pointeur temporaire. Puisque p_queue pointe la variable file, alors (*p_queue) est cette variable, c'est à dire l'adresse du maillon en queue de la file. Et puisque la liste est circulaire, alors (*p_queue)->next contient l'adresse du maillon de tête. On écrira donc :
   fifo_t ptr_tete = (*p_queue)->next; // tmp pointe la tête de file
   

   

3. Indiquer que la tête devient l'ancien second maillon et faire que le maillon de queue pointe cette nouvelle tête (circularité). Puisque ptr_tete pointe la tête actuelle, l'adresse du nouveau maillon de tête est ptr_tete->next. On écrira donc :
   (*p_queue)->next = ptr_tete->next ;
   

   

4. Libérer l'ancien maillon de tête, avec free(ptr_tete);

   

5. Retourner la valeur de l'élément qui était en tête avec return elt_tete;

   

... et voila, pour le cas général, le tour est joué.

Vous remarquerez peut-être que cet algorithme ne modifie pas la variable file pointée par q_queue. C'est normal : dans le cas général où la file contient plusieurs éléments, la queue de file reste la même après le défilage et la variable file n'a pas à être mise à jour.

3.6.2 Cas particulier "défiler une file à 1 élément"

Dans le cas "file à 2 éléments", vous pourrez vérifier que l'algorithme qui précède fonctionne sans problème.

Le cas particulier "file vide", n'a lui pas à être considéré. En effet, le contrat de la fonction annonce comme précondition "la liste n'est pas vide". Il suffira donc de vérifier cette précondition au début de la fonction en appelant assert(), et ce sera très bien comme cela.

Le cas où "file n'a qu'un unique élément" est plus délicat.

En effet, partant de l'état initial :

il faut qu'après l'exécution de la fonction fifo_dequeue() la file ait été ramené à l'état "file vide" :

Pour cela, dans ce cas particulier "file vide", il faut que la fonction fifo_dequeue() :

• 1. Mette de côté la valeur de l'élément contenu dans le maillon de tête, pour pouvoir le retourner à la fin. Comme précédemment :
  element_t elt_tete = fifo_peek(*p_queue);
• 2. Libére l'ancien maillon (le seul de la file), avec :
  free( (*p_queue) );
• 3. Mette à NULL la variable file pour indiquer que la file devient vide. Fort heureusement, l'adresse de cette variable du main est passée par pointeur à la fonction fifo_dequeue(). On écrira donc :
  (*p_queue) = NULL ; // met à jour la variable qui stocke la file hors de la fonction fifo_dequeue()
• 4. Et enfin, retourne la valeur de l'élément qui était en tête avec :
  return elt_tete;

3.6.3 L'algorithme de défilage en pseudo code

En pseudo code, l'algorithme de défilage s'écrit donc :

          // algorithme de défilage dans l'implémentation "liste circulaire"
          verifier la précondition "la liste n'est pas vide"
          si (la file n'a qu'un élément) {// bien réfléchir à comment exprimer "la file n'a qu'un élément"
            elt_tete = valeur stockée dans la tête de la file
            libérer l'unique maillon
            affecter NULL à la variable file de la fonction appelante
            retourner elt_tete
          }
          elt_tete  = valeur stockée dans la tête de la file
          tmp_tete = adresse du maillon de tete
          dans le maillon de queue, indiquer que le maillon suivnat est   tmp_tete->next
          libérer la mémoire allouée pour tmp_tete
          retourner elt_tete
        

Rappel : nous ne donnerons pas dans cette fiche le code C de la fonction fifo_dequeue(). A vous de l'écrire en TD et TP !

4. En conclusion