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.
Cette seconde approche ne résout pas entièrement le problème puisqu'une place, éventuellement non négligeable, sera occupée en début de tableau, sans aucun but. Si la file est de taille fixe, il est possible de réaliser des déplacements circulaires des positions de début et fin. C'est-à-dire que lorsqu'un ajout est effectué alors que le dernier élément du tableau vient d'être occupé, si le premier élément est libre, c'est celui-ci qui deviendra la nouvelle fin de la liste. Cette opération est réalisée assez simplement à l'aide de l'opérateur modulo.
Si au contraire la taille est dynamique, un redimensionnement du tableau par ses bornes inférieure et supérieure est souhaitable. Ces bornes correspondent alors respectivement aux positions de début et de fin. 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. - QPut(Data) : Ajoute un élément (Data) à la file
- QGet() : Retire un élément de la file
- Peek() : Consulte l'élément en tête de la file
- Count : Détermine le nombre d'éléments dans la file
Les points importants de l'implémentation sont les suivants : - Lorsqu'un accès est réalisé à la file, les positions sont toujours calculées modulo la taille du tableau. Ceci permet d'utiliser un tableau de taille fixe pour toutes les opérations.
- Le tableau interne a ici une taille fixe. Il est donc important de vérifier à chaque ajout si suffisamment de place est disponible et d'informer l'utilisateur le cas échéant.
Option Explicit
Private Const QUEUE_SIZE As Long = 256
Private mQueue(QUEUE_SIZE - 1) As Long
Private mCount As Long
Private mHead As Long
Public Function QPut(Data As Long) As Boolean
QPut = (mCount <> QUEUE_SIZE)
If QPut Then
mQueue((mHead + mCount) Mod QUEUE_SIZE) = Data
mCount = mCount + 1
End If
End Function
Public Function QGet() As Long
If (mCount <> 0) Then
QGet = mQueue(mHead)
mHead = (mHead + 1) Mod QUEUE_SIZE
mCount = mCount - 1
End If
End Function
Public Function Peek() As Long
If (mCount <> 0) Then
Peek = mQueue(mHead)
End If
End Function
Public Function Count()
Count = mCount
End Function
Private Sub Class_Initialize()
mCount = 0
mHead = 0
End Sub La fonction suivante présente un exemple d'utilisation : Sub Test()
Dim a As Queue
Set a = New Queue
a.QPut 1
a.QPut 2
a.QPut 3
a.QPut 4
Debug.Print a.Peek
Debug.Print a.Peek
Do While (a.Count <> 0)
Debug.Print a.QGet
Loop
End Sub Voir aussi : |
Top