Question 159

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 file

Les 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éalisation

Sous 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
    'Vérifie qu'il y a encore de la place pour le prochain élément
    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
    'Vérifie s'il y a encore des éléments à extraire
    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
    'Vérifie s'il y a des éléments présents
    If (mCount <> 0) Then
        Peek = mQueue(mHead)
    End If
End Function

Public Function Count()
    Count = mCount
End Function

Private Sub Class_Initialize()
    'Indique qu'il n'y a pas encore d'éléments présents
    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 '1
    Debug.Print a.Peek '1
    
    Do While (a.Count <> 0)
        Debug.Print a.QGet '1 2 3 4
    Loop
End Sub

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