Comment implémenter une file (ou queue) ? Comment implémenter une FIFO en Visual Basic ?Une file, ou queue, est une structure permettant de stocker des données, le premier élément ajouté étant le premier sorti (FIFO - first in, first out). L'usage des files est très répandu, dès lors qu'une communication structurée doit être transmise. C'est le cas, par exemple lorsque deux processus doivent communiquer. Le protocole TCP, sur lequel reposent HTTP, FTP, POP3, SMTP, etc., en est une spécification. Ce sont aussi des files qui sont utilisées lorsque des données doivent être stockées ou traitées de manière séquentielle. Structure d'une fileLes données contenues dans une file sont conservées dans une liste liée, ou dans un tableau dynamique. Les éléments de la file sont directement les éléments du tableau ou de la liste. Les accès aux éléments se font principalement en retrait d'élément (Get), ajout d'élément (Put), et consultation de l'élément du début de la file (Peek). Dans certaines situations où c'est possible, la longueur de la file (Count) est aussi accessible. Dans le cas des tableaux, un problème se pose. Lorsqu'une donnée vient à être consultée, elle est retirée de la file afin de pouvoir lire la donnée suivante. Une approche naïve consisterait à recopier tous les éléments suivants, afin d'occuper l'espace de l'élément manquant. Cette solution serait peu performante. Il s'agit de maintenir une position de tête de liste, en même temps qu'une position de fin de liste. Dans le cas des listes liées, il s'agit de conserver une référence au premier et au dernier élément de la liste. La lecture est réalisée sur l'élément de tête, celui-ci étant supprimé après lecture. L'ajout se fait de manière similaire en ajoutant un élément en fin de liste. RéalisationSous Visual Basic, la manière la plus courante d'employer une file est sous la forme d'un moyen de communication spécialisé. Ceci inclus l'utilisation du composant Winsock en TCP, de services tels que MSMQ ou MQSeries, ou encore des services basés sur des files tels que Inet — réalisant des transactions HTTP et FTP sur base de TCP — et RPC — pour déclencher des actions sur des objets distants, MSMQ étant le support. Pour la persistance ordonnée des données, les instructions Get et Put, en mode binaire, sont de la même manière le service approprié. Il est important de remarquer la nomenclature de Get et Put, puisqu'il s'agit du nom classiquement attribué dans l'accès à n'importe quelle file. Lorsque de tels services sont disponibles, il est très préférable de les utiliser, ces solutions ayant été conçues pour être performantes et étudiées pour offrir suffisamment de confort à leur utilisateur. Il reste que certains cas ne sont pas couverts par des solutions existantes, ou ne le sont pas à coût et/ou facilité d'installation raisonnable. Nous vous proposons donc un exemple d'implémentation classique de file, de taille fixe, offrant les méthodes suivantes où nous choisissons que Data sera un Long. Il est bien entendu possible d'implémenter la même structure pour stocker tout autre type de données.
Les points importants de l'implémentation sont les suivants :
Option Explicit La fonction suivante présente un exemple d'utilisation : Sub Test() Voir aussi : |
Date de publication : 13 septembre 2007 Dernière modification : 13 septembre 2007 Rubriques : Structures de données Mots-clés : structure, queue, file, put, get, structuré, séquentiel, séquence |