Question 158

Comment implémenter une pile (ou stack) ? Comment implémenter une LIFO en Visual Basic ?

Un stack, ou pile, est une structure permettant de stocker des données, le dernier élément ajouté étant le premier sorti (LIFO - last in, first out). L'analogie la plus courante est cette d'une pile d'assiette : il est possible d'empiler autant d'assiettes qu'on veut, mais on ne peut reprendre que celle du dessus. Que ce soient les boutons "Annuler" et "Refaire", les calculatrices employant la notation polonaise inverse (NPI), les pages précédentes et suivantes d'un navigateur web, les algorithmes de recherche de chemin, ou plus généralement toute opération demandant d'enregistrer un contexte pour ensuite le restaurer, c'est cette structure de données qui est préférée.

Une erreur fréquente lors d'une erreur d'implémentation de procédures récursives est un dépassement de pile ("Out of stack space"). La pile en question préserve avant chaque nouvel appel de fonction le contexte d'exécution de la fonction appelante. Ce contexte comprend notamment la valeur des différentes variables.

Structure d'une pile

Les données contenues dans un stack sont stockées dans une liste liée, ou dans un tableau dynamique. Les éléments de la pile 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 (Pop), ajout d'élément (Push), consultation de l'élément du haut de la pile (Peek), et de la hauteur de la pile (Count).

Dans le cas des tableaux, une variable est chargée de maintenir la position du haut de la pile. Cette variable est très souvent nommée "pointeur de tête", en référence au véritable pointeur sur le dernier élément lors d'une implémentation classique d'une pile en C. Lorsqu'un élément est ajouté (poussé) dans la pile, il suffit d'incrémenter le pointeur de tête afin de pointer vers un nouvel emplacement libre du tableau et de copier la donnée à cet endroit. De même, pour effectuer un retrait de la pile, il suffit de retirer l'élément indiqué par le pointeur de tête et de décrémenter ce dernier.

Dans le cas de listes liées, la manipulation peut être faite de manière similaire au cas du tableau. Au lieu de conserver la position du haut de la pile, on conservera une référence au dernier élément de liste. C'est un usage commode de la liste liée, mais non le plus performant pour ce cas.

La structure d'une liste liée nous permet en effet de faire correspondre l'élément de tête de la liste au pointeur de tête de la pile. Cela signifie que les insertions, retrait et consultation se font au niveau de l'élément de tête de liste. Il n'est alors aucunement nécessaire de parcourir les différents liens de la liste pour réaliser ces opérations. Ce type d'implémentation est donc plus approprié, bien que moins intuitif.

Réalisation

Nous implémenterons une pile, de taille maximale fixe, exposant 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.

• Push(Data) : Ajoute un élément (Data) sur la pile
• Pop() : Retire un élément de la pile
• Peek() : Consulte l'élément en tête de la pile
• Count : Détermine le nombre d'éléments sur la pile

Les points importants de l'implémentation sont les suivants :

• Le pointeur de tête (ici mHead) est modifié dans les deux méthodes Push et Pop. Le pointeur de tête étant la position de l'élément de tête dans le tableau, le nombre d'éléments présents dans la pille y correspond directement.
• 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

Public Const STACK_MAX_SIZE As Long = 256
Private mStack(STACK_MAX_SIZE-1) As Long
Private mHead As Long

Public Function Push(Data As Long) As Boolean
    'Vérifie qu'il y a encore de la place pour le prochain élément
    Push = (mHead < STACK_MAX_SIZE - 1)
    
    If Push Then
        mHead = mHead + 1
        mStack(mHead) = Data
    End If
End Function

Public Function Pop() As Long
    'Vérifie s'il y a encore des éléments à extraire
    If (mHead > -1) Then
        Pop = mStack(mHead)
        mHead = mHead - 1
    End If
End Function

Public Function Peek() As Long
    'Vérifie s'il y a des éléments présents
    If (mHead > -1) Then
        Peek = mStack(mHead)
    End If
End Function

Public Function Count()
    Count = mHead + 1
End Function

La méthode suivante présente un exemple d'utilisation :

Sub Test()
    Dim MyStack As Stack
    
    Set MyStack = New Stack
    
    MyStack.Push 1
    MyStack.Push 2
    MyStack.Push 4
    MyStack.Push 7
    Debug.Print(MyStack.Pop) '7
    Debug.Print(MyStack.Pop) '4

    MyStack.Push 3
    MyStack.Push 4
    MyStack.Push 5
    
    Debug.Print MyStack.Peek '5
    Debug.Print MyStack.Peek '5
    
    Do While (MyStack.Count <> 0)
        Debug.Print MyStack.Pop '5 4 3 2 1
    Loop
End Sub

Voir aussi :

• Comment implémenter et utiliser les structures de données classiques ?
• Comment réaliser et utiliser une liste sur base d'un tableau dynamique ?
• Comment réaliser et utiliser une liste liée (ou liste chaînée) ?