Man page - queue(7)

Packages contains this manual

Package: manpages
apt-get install manpages

Manuals in package:

Documentations in package:

manpages

Available languages:

en fr ro

Manual

queue

NOM
DESCRIPTION
Listes simplement chaînées (SLIST)
Files d’attente finies simplement chaînées (STAILQ)
Structures de données doublement chaînées
Listes doublement chaînes (LIST)
Files d’attente finies doublement chaînées (TAILQ)
Files d’attente circulaires doublement chaînées (CIRCLEQ)
STANDARDS
HISTORIQUE
NOTES
VOIR AUSSI
TRADUCTION

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 .