Implementing a Stack


The easiest way to implement a stack is to use an internal Collection. You ­simply add new members to the end of the Collection in the Push method and take them off the end in the Pop method:

‘ CStackCol implements IStack
Implements IStack
Private stack As Collection

Private Sub Class_Initialize()
    Set stack = New Collection
End Sub

Private Sub IStack_Push(vArg As Variant)
    stack.Add vArg
End Sub

Private Function IStack_Pop() As Variant
    If stack.Count Then
        If IsObject(stack(stack.Count)) Then
            Set IStack_Pop = stack(stack.Count)
        Else
            IStack_Pop = stack(stack.Count)
        End If
        stack.Remove stack.Count
    End If
End Function

Private Property Get IStack_Count() As Long
    IStack_Count = stack.Count
End Property

The Collection version is easy to implement, and its performance isn’t bad—for a small stack. The problem with the Collection-based stack is that it slows way down if you push too many things onto it. This isn’t really surprising. Implementing IStack with a Collection is like shooting ducks with a grenade launcher.


A linked list might be more appropriate. I won’t show the implementation because it looks a lot like a simplified version of the CList code you’ve already seen. Check it out for yourself in STACKLST.CLS.


The list version is a little slow for small stacks, but its speed is constant. In fact, it turns out to be a lot faster than the Collection version for large stacks. Also, it doesn’t waste data space like this vector version:

Private av() As Variant
Private Const cChunk = 10
Private iLast As Long, iCur As Long
Private Sub IStack_Push(vArg As Variant)
    iCur = iCur + 1
    On Error GoTo FailPush
    If IsObject(vArg) Then
        Set av(iCur) = vArg
    Else
        av(iCur) = vArg
    End If
    Exit Sub
FailPush:
    iLast = iLast + cChunk  ‘ Grow
    ReDim Preserve av(1 To iLast) As Variant
    Resume                  ‘ Try again
End Sub

Private Function IStack_Pop() As Variant
    If iCur Then
        If IsObject(av(iCur)) Then
            Set IStack_Pop = av(iCur)
        Else
            IStack_Pop = av(iCur)
        End If
        iCur = iCur - 1
        If iCur < (iLast - cChunk) Then
            iLast = iLast - cChunk      ‘ Shrink
            ReDim Preserve av(1 To iLast) As Variant
        End If
    End If
End Function

Private Property Get IStack_Count() As Long
    IStack_Count = iCur
End Property

The vector version is the most complicated and has the most lines of code, but don’t let that fool you. It’s far and away the fastest, as the Performance sidebar on the facing page shows. It does waste a little data space, but you can adjust that by changing the cChunk constant. In fact, if you set cChunk to 1, you won’t waste any data space and you’ll still be faster than the other versions—even though you’ll be resizing the array for every push and pop.

Problem: Compare the speed of stacks based on Collections, linked lists, and vectors.
Problem P-Code Native Code
Use Collection stack of 500 numbers 0.1161 sec 0.0853 sec
Use Collection stack of 5000 numbers 10.0181 sec 9.3406 sec
Use linked list stack of 500 numbers 0.1357 sec 0.0972 sec
Use linked list stack of 5000 numbers 1.3360 sec 1.0265 sec
Use vector stack of 500 numbers 0.0294 sec 0.0162 sec
Use vector stack of 5000 numbers 0.2929 sec 0.1597 sec


Conclusion: Not even close. Vectors win by several laps. The CStack class in VBCore is a noninterface version of CStackVec.