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

       BSD.

HISTORIQUE

       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 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.

Pages du manuel de Linux 6.9.1                     2 mai 2024                                           queue(7)