queue(7)

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.