Zeiger in VB - Seite 5

Ein Stapel  

Die Container-Schnittstelle

Um zu demonstrieren, wie vielfältig diese Schnittstelle ist, folgt hier der Quelltext einer anderen Containerklasse, des so genannten Stapels ("Stack"). Dieser Container nimmt ebenfalls Elemente auf, gibt sie aber in umgekehrter Reihenfolge wieder: das zuerst eingefügte Element ist das zuletzt ausgegebene (auf Englisch "first in, last out"). Obwohl er somit grundverschieden von der Warteschlage ist, besitzt er die selbe Schnittstelle. Man kann die Schnittstelle also abstrahieren:

' IContainer

Public Sub Clear(): End Sub
Public Sub Push(Item As String): End Sub
Public Function Pop() As String: End Function
Public Property Get Peek() As String: End Property
Public Property Get Size() As Long: End Property
Public Function Clone() As IContainer: End Function

Listing 9

Der Stapel

... aber das nur am Rande. Zurück zu unserem Stapel; natürlich lässt er sich auch über Zeiger implementieren. Ich werde außerdem die oben stehende Interface verwenden. Es gibt auch andere, zeigerlose Implementierungen eines Stapels, die ebenfalls recht schnell sind (um genau zu sein: ein einfaches Feld reicht aus), aber die Implementierung mit Zeigern ist ebenfalls recht interessant, weil sie auch auf Listen aufbaut; im Gegensatz zur Warteschlange reicht hier jedoch eine einfach gegliederte Liste, d.h. das Element Prev_ entfällt, genauso wie m_Last.

' Stack.cls
   Option Explicit

   Implements IContainer

   Private m_Top   As Long
   Private m_Count As Long
   '----------------------------------------------------

   Private Sub Class_Terminate()
       Call IContainer_Clear
   End Sub
   '----------------------------------------------------

   Private Sub IContainer_Clear()
       Dim pIter As Long
       
       Do While m_Top
           pIter = m_Top
           m_Top = Heap(m_Top).Seg.Next_
           Call Free(pIter)
       Loop
       
       m_Count = 0
   End Sub

   Private Function IContainer_Clone() As IContainer
       Dim pIter As Long
       Dim Steps As Long
       Dim I     As Long
       
       Set IContainer_Clone = New Stack
       
       Steps = m_Count
       
       Do While Steps > 0
           pIter = m_Top
           For I = 1 To Steps - 1
               pIter = Heap(pIter).Seg.Next_
           Next I
           
           Call IContainer_Clone.Push(Heap(pIter).Seg.Content)
           Steps = Steps - 1
       Loop
   End Function

   Private Sub IContainer_Push(Item As String)
       If m_Count = 0 Then
           m_Top = Alloc()
           Heap(m_Top).Seg.Content = Item
       Else
           Dim pTmp As Pointer
           
           pTmp = Alloc()
           Heap(pTmp).Seg.Content = Item
           Heap(pTmp).Seg.Next_ = m_Top
           m_Top = pTmp
       End If
       
       m_Count = m_Count + 1
   End Sub

   Private Function IContainer_Pop() As String
       If m_Count > 0 Then
           Dim pTmp As Pointer
           
           pTmp = m_Top
           
           IContainer_Pop = Heap(m_Top).Seg.Content
           m_Top = Heap(m_Top).Seg.Next_
           Call Free(pTmp)
           
           m_Count = m_Count - 1
       End If
   End Function

   Private Property Get IContainer_Peek() As String
       If m_Count > 0 Then _
           IContainer_Peek = Heap(m_Top).Seg.Content
   End Property

   Private Property Get IContainer_Size() As Long
       IContainer_Size = m_Count
   End Property

Listing 10

Natürlich müssen wir den Heap mit einem eigenen StackItem-Typ definieren:

Public Type StackItem
    Content As String
    Next_   As Long
End Type

Listing 11

Funktionsbeispiel

Folgendes einfaches Beispiel demonstriert die Verwendung des Stacks:

Sub Main()
    Call SetHeapSize(10)
    
    Dim MyStack As IContainer
    Dim Word    As Variant
    
    Set MyStack = New Stack
    
    For Each Word In Split("This phrase will be printed in reverse order.")
        Call MyStack.Push(CStr(Word))
    Next Word
    
    Do While MyStack.Size > 0
        Debug.Print MyStack.Pop(); " ";
    Loop
End Sub

Listing 12

Zum Download des Beispielcodes.