queue(7) Miscellaneous Information Manual queue(7) NOM queue - implementations de listes et de files d'attente chainees DESCRIPTION Le fichier d'en-tete fournit un ensemble de macros qui definissent et operent sur les structures suivantes : SLIST Listes simplement chainees LIST Liste doublement chainees STAILQ Files d'attente finies simplement chainees TAILQ Files d'attente finies doublement chainees CIRCLEQ Files d'attente circulaires doublement chainees Toutes les structures prennent en charge les fonctionnalites suivantes : - insertion d'un nouvel element en tete de liste ; - insertion d'un nouvel element apres n'importe quel element dans la liste ; - 0(1) suppression d'un element en tete de liste ; - traversee en avant de la liste. La taille du code et le temps d'execution dependent de la complexite de la structure de donnees utilisee, aussi les programmeurs doivent choisir avec soin celle appropriee. Listes simplement chainees (SLIST) Les listes simplement chainees sont les plus simples et ne prennent en charge que les fonctionnalites ci-dessus. Elles sont ideales pour les applications avec de grands jeux de donnees et peu ou pas de suppressions, ou pour mettre en oeuvre une pile LIFO. Elles ajoutent la fonctionnalite suivante : - O(n) suppression de n'importe quel element de la liste. Files d'attente finies simplement chainees (STAILQ) Les files d'attente finies simplement chainees ajoutent les fonctionnalites suivantes : - des elements peuvent etre ajoutes en fin de liste ; - O(n) suppression de n'importe quel element de la liste. - les elements peuvent etre concatenes. Cependant : - toutes les insertions doivent indiquer la tete de la liste ; - chaque element de tete de liste necessite deux pointeurs au lieu d'un seul. Les files d'attente finies simplement chainees sont ideales pour les applications avec de grands jeux de donnees et peu ou pas de suppressions, ou pour mettre en oeuvre une file FIFO. Structures de donnees doublement chainees De plus, tous les types doublement chaines de structures de donnees (listes et files d'attente finies) permettent : - l'insertion d'un nouvel element avant n'importe quel element de la liste ; - O(1) suppression de n'importe quel element de la liste. Cependant : - chaque element necessite deux pointeurs au lieu d'un seul. Listes doublement chaines (LIST) Les listes chainees sont la forme la plus simple des structures de donnees doublement chainees. Elles ajoutent la fonctionnalite suivante a celles ci-dessus : - elles peuvent etre traversees en arriere. Cependant : - Pour une traversee en arriere, un element de debut de traversee et la liste a laquelle il appartient doivent etre indiquees. Files d'attente finies doublement chainees (TAILQ) Les files d'attente finies ajoutent les fonctionnalites suivantes : - des elements peuvent etre ajoutes en fin de liste ; - elles peuvent etre traversees en arriere, de la queue a la tete ; - les elements peuvent etre concatenes. Cependant : - toutes les insertions et suppressions d'element de liste doivent mentionner la tete de la liste ; - chaque element de tete de liste necessite deux pointeurs au lieu d'un seul. Files d'attente circulaires doublement chainees (CIRCLEQ) Les files d'attente circulaires ajoutent la fonctionnalite suivante a celles ci-dessus : - le premier et le dernier element sont connectes. Cependant : - La condition terminale pour la traversee est plus complexe. STANDARDS BSD. HISTORIQUE Les macros sont apparues dans 4.4BSD. NOTES Quelques BSD fournissent SIMPLEQ au lieu de STAILQ. Elles sont identiques, mais pour des raisons historiques elles ont ete nommees differemment selon les BSD. STAILQ tire son origine de FreeBSD et SIMPLEQ de NetBSD. Pour des raisons de compatibilite, certains systemes fournissent les deux. La glibc fournit STAILQ et SIMPLEQ qui sont identiques a l'exception d'un equivalent SIMPLEQ a STAILQ_CONCAT() manquant. VOIR AUSSI circleq(3), insque(3), list(3), slist(3), stailq(3), tailq(3) TRADUCTION La traduction francaise de cette page de manuel a ete creee par Christophe Blaess , Stephan Rafin , Thierry Vignaud , Francois Micaux, Alain Portal , Jean-Philippe Guerard , Jean-Luc Coulon (f5ibh) , Julien Cristau , Thomas Huriaux , Nicolas Francois , Florentin Duneau , Simon Paillard , Denis Barbier et David Prevot Cette traduction est une documentation libre ; veuillez vous reporter a la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITE LEGALE. Si vous decouvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message a . Pages du manuel de Linux 6.06 31 octobre 2023 queue(7)