# Queue.h ou quand les listes chaînées deviennent si simple !.md

Queue.h est un outil indispensable à maîtriser quand l''on développe beaucoup en langage C. C''est une suite de macro qui facilite la création et l''utilisation des listes chaînées. On y distingue trois ensembles de macro pour les listes simples, les files (FIFO/LIFO) et les listes circulaires.', ' En C, la liste chaînée fait souvent office d''un apprentissage laborieux, douloureux. A deux pas entre la maitrise des pointeurs et l''élaboration de structures, c''est un moyen simple et efficace pour la gestion et l''accès aux données d''un programme. Grâce aux listes plus besoin de tableau, on raccourcie ces structures et on donne un air artistique à son code.

Après les avoir utilisés un certain temps, on se rend vite compte que l''on ne peut plus s''en passer - malgré parfois le besoin d''élaborer des structures plus complexes comme des arbres binaires de toutes sortent ou des graphes - on aime en mettre partout pour tout faire. C''est à ce moment que l''on se rend compte que le temps de développement d''une liste chaînée coûte cher.

Il faut faire la structure, mettre en place une seconde structure pour la gestion de la liste (notamment pour les listes à double sens), gérer les insertions et les suppressions de maillons et même les affichages. Avec un peu de chance, ça compilera la troisième fois. Bref, ça prend du temps et ce temps précieux pourrait être utilisé à faire avancer l''ensemble du projet plutôt que trois fichiers d''entêtes et deux fichiers C.

Que nous dit le man 3 queue ? sys/queue.h est un ensemble de macro facilitant l''insertion, le parcours et la suppression d''éléments d''une liste. On peut y lire que la taille du code est environ 15 % meilleur dans le cas d''une file et 40 % meilleur dans le cas d''une liste circulaire. Il y a aussi une note comparative à propos de la vitesse d''exécution par rapport à une liste, mais qui s''en préoccupe quand on code en C# ou Java ?

Un des avantages de ces macros est qu''on peut les emmener partout où l''on code en C. Si jamais une architecture un peu particulière (je pense à SunOS) qui ne vous permet pas de trouver le fichier à inclure, il vous suffira de copier/coller le fichier dans vos sources.

• 24-11-2012 - https://web.archive.org/web/20130330153803/http://cavaencoreparlerdebits.fr/openblog/post/queue-h-ou-quand-les-listes-chainees-deviennent-si-simple

main.c

#ifndef HEADER_H
#define HEADER_H

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

/*
 * On inclut notre fichier header queue.h
 */
#include <sys/queue.h>

/*
 * On définit notre structure
 */
typedef struct MaStruct {
  /*
   * Ici on met nos éléments par exemple :
   * str la chaine de caractère.
   */
  char *str;

  /*                    
   * On déclare notre liste avec SLIST_ENTRY qui est équivalente à :
   * struct { struct MaStruct *sle_next; } next;           
   */
  SLIST_ENTRY(MaStruct) next;
} MaStruct;

#endif /* HEADER_H */

int                             main(void)
{
 /*
  * On définit notre structure.
  */
  SLIST_HEAD(, MaStruct)        head;
  MaStruct                      *p;

 /*
  * On initialise notre structure de liste.
  */
  SLIST_INIT(&head);

 /*
  * On alloue notre pointeur p qui sera un maillon à insérer dans la liste.
  * On fait de même pour allouer dans notre structure la chaine str et on ajoute sa valeur.
  */
  p = malloc(sizeof(*p));
  p->str = malloc(sizeof(char) * (strlen("exemple1") + 1));
  strcpy(p->str, "exemple1\0");

 /*
  * On insert le nouveau maillon dans notre structure, on indique que next est le pointeur
  * vers le prochain maillon.
  */
  SLIST_INSERT_HEAD(&head, p, next);

  p = malloc(sizeof(*p));
  p->str = malloc(sizeof(char) * (strlen("exemple2") + 1));
  strcpy(p->str, "exemple2\0");

  SLIST_INSERT_HEAD(&head, p, next);

 /*
  * On parcourt notre liste grâce à une macro foreach adapter à notre liste.
  */
  SLIST_FOREACH(p, &head, next) {
    printf("element : %s\n", p->str);
  }

 /*
  * Pour la suppression, on utilise la macro empty de notre type de liste.
  */
  while (!SLIST_EMPTY(&head))
    {
      /* On pointe le premier maillon pour ne pas le perdre en mémoire. */
      p = SLIST_FIRST(&head);

      /* On supprime de la liste notre premier maillon et le deuxième prend sa place. */
      SLIST_REMOVE_HEAD(&head, next);

      /* Enfin on libère la mémoire. */
      free(p->str);
      free(p);
    }

  return (0);
}