NOM

       queue – implémentations de listes et de files d'attente chaînées

DESCRIPTION

       Le  fichier  d’en-tête  <sys/queue.h>  fournit  un  ensemble  de macros qui définissent et
       opèrent sur les structures suivantes :

       SLIST  Listes simplement chaînées

       LIST   Liste doublement chaînées

       STAILQ Files d'attente finies simplement chaînées

       TAILQ  Files d'attente finies doublement chaînées

       CIRCLEQ
              Files d'attente circulaires doublement chaînées

       Toutes les structures prennent en charge les fonctionnalités suivantes :

       -  insertion d'un nouvel élément en tête de liste ;

       -  insertion d'un nouvel élément après n'importe quel élément dans la liste ;

       -  0(1) suppression d'un élément en tête de liste ;

       -  traversée en avant de la liste.

       La taille du code et le temps d’exécution dépendent de la complexité de  la  structure  de
       données utilisée, aussi les programmeurs doivent choisir avec soin celle appropriée.

   Listes simplement chaînées (SLIST)
       Les  listes  simplement  chaînées  sont  les plus simples et ne prennent en charge que les
       fonctionnalités ci-dessus. Elles sont idéales pour les applications avec de grands jeux de
       données  et  peu  ou  pas  de  suppressions,  ou pour mettre en œuvre une pile LIFO. Elles
       ajoutent la fonctionnalité suivante :

       -  O(n) suppression de n'importe quel élément de la liste.

   Files d'attente finies simplement chaînées (STAILQ)
       Les files d'attente finies simplement chaînées ajoutent les fonctionnalités suivantes :

       -  des éléments peuvent être ajoutés en fin de liste ;

       -  O(n) suppression de n'importe quel élément de la liste.

       -  les éléments peuvent être concaténés.

       Cependant :

       -  toutes les insertions doivent indiquer la tête de la liste ;

       -  chaque élément de tête de liste nécessite deux pointeurs au lieu d'un seul.

       Les files d'attente finies simplement chaînées sont idéales pour les applications avec  de
       grands  jeux  de  données  et peu ou pas de suppressions, ou pour mettre en œuvre une file
       FIFO.

   Structures de données doublement chaînées
       De plus, tous les types doublement chaînés de  structures  de  données  (listes  et  files
       d'attente finies) permettent :

       -  l’insertion d'un nouvel élément avant n'importe quel élément de la liste ;

       -  O(1) suppression de n'importe quel élément de la liste.

       Cependant :

       -  chaque élément nécessite deux pointeurs au lieu d'un seul.

   Listes doublement chaînes (LIST)
       Les  listes  chaînées  sont  la  forme la plus simple des structures de données doublement
       chaînées. Elles ajoutent la fonctionnalité suivante à celles ci-dessus :

       -  elles peuvent être traversées en arrière.

       Cependant :

       -  Pour une traversée en arrière, un élément de début de traversée et la liste à  laquelle
          il appartient doivent être indiquées.

   Files d'attente finies doublement chaînées (TAILQ)
       Les files d'attente finies ajoutent les fonctionnalités suivantes :

       -  des éléments peuvent être ajoutés en fin de liste ;

       -  elles peuvent être traversées en arrière, de la queue à la tête ;

       -  les éléments peuvent être concaténés.

       Cependant :

       -  toutes  les insertions et suppressions d’élément de liste doivent mentionner la tête de
          la liste ;

       -  chaque élément de tête de liste nécessite deux pointeurs au lieu d'un seul.

   Files d'attente circulaires doublement chaînées (CIRCLEQ)
       Les files d'attente circulaires ajoutent la fonctionnalité suivante à celles ci-dessus :

       -  le premier et le dernier élément sont connectés.

       Cependant :

       -  La condition terminale pour la traversée est plus complexe.

STANDARDS

       Absentes de POSIX.1, POSIX.1-2001 et POSIX.1-2008, présentes  dans  les  BSD.  Les  macros
       <sys/queue.h> sont apparues dans 4.4BSD.

NOTES

       Quelques  BSD  fournissent SIMPLEQ au lieu de STAILQ. Elles sont identiques, mais pour des
       raisons historiques elles ont été nommées différemment selon  les  BSD.  STAILQ  tire  son
       origine  de  FreeBSD  et  SIMPLEQ  de  NetBSD. Pour des raisons de compatibilité, certains
       systèmes fournissent les deux. La glibc fournit STAILQ et SIMPLEQ qui  sont  identiques  à
       l’exception d’un équivalent SIMPLEQ à STAILQ_CONCAT() manquant.

VOIR AUSSI

       circleq(3), insque(3), list(3), slist(3), stailq(3), tailq(3)

TRADUCTION

       La  traduction  française  de  cette  page  de  manuel  a  été créée par Christophe Blaess
       <https://www.blaess.fr/christophe/>, Stéphan  Rafin  <stephan.rafin@laposte.net>,  Thierry
       Vignaud  <tvignaud@mandriva.com>,  François Micaux, Alain Portal <aportal@univ-montp2.fr>,
       Jean-Philippe   Guérard   <fevrier@tigreraye.org>,   Jean-Luc   Coulon   (f5ibh)    <jean-
       luc.coulon@wanadoo.fr>,    Julien    Cristau    <jcristau@debian.org>,    Thomas   Huriaux
       <thomas.huriaux@gmail.com>, Nicolas François <nicolas.francois@centraliens.net>, Florentin
       Duneau  <fduneau@gmail.com>, Simon Paillard <simon.paillard@resel.enst-bretagne.fr>, Denis
       Barbier <barbier@debian.org> et David Prévot <david@tilapin.org>

       Cette traduction est une documentation libre ; veuillez vous reporter  à  la  GNU  General
       Public   License   version 3  ⟨https://www.gnu.org/licenses/gpl-3.0.html⟩  concernant  les
       conditions de copie et de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE.

       Si vous découvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un
       message à ⟨debian-l10n-french@lists.debian.org⟩.