queue(7) Miscellaneous Information Manual queue(7)

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

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

Listes simplement chaînées
Liste doublement chaînées
Files d'attente finies simplement chaînées
Files d'attente finies doublement chaînées
Files d'attente circulaires doublement chaînées

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

5 février 2023 Pages du manuel de Linux 6.03