The StackItem Class

  • Article

It doesn't get much simpler than this. The StackItem class maintains a data item, as well as a pointer to the next item in the structure, as shown in Listing 6.1.

Listing 6.1: Code for the StackItem Class

' Keep track of the next stack item,
' and the value of this item.
Public Value As Variant
Public NextItem As StackItem

The Stack Class

The StackItem class contains a single item, a pointer to the first item in the stack (the stack top). That pointer always points to the top of the stack, and it's at this location that you'll add (push) and delete (pop) items from the stack. The Stack class module implements the two methods (Push and Pop), as well as two read-only properties, StackTop (which returns the value of the element at the top of the stack, without popping the item) and StackEmpty (which returns a Boolean value indicating the status of the stack–True if there are no items in the stack and False if there are items).

Pushing Items onto the Stack

To add an item to the stack, you “push” it to the top of the stack. This is similar to pushing a new cafeteria tray to the top of the tray stack. When you push the new tray, each of the other trays moves down one position in the stack. Using linked lists, the code must follow these steps:

  1. Create the new node.

  2. Place the value to be stored in the new node.

  3. Make the new node point to whatever the current stack top pointer refers to.

  4. Make the stack top point to this new node.

The code in Listing 6.2 shows the Push method of the stack class. The four lines of code correspond to the four steps listed above.

Listing 6.2: Use the Push Method to Add a New Item to the Stack

Public Sub Push(ByVal varText As Variant)
    ' Add a new item to the top of the stack.

    Dim siNewTop As New StackItem

    siNewTop.Value = varText
    Set siNewTop.NextItem = siTop
    Set siTop = siNewTop
End Sub

Figures 6.5 and 6.6 demonstrate the steps involved in pushing an item onto a stack. In the example case, you're attempting to push the value 27 onto a stack that already contains three elements.

Figure 6.5: The first three steps in pushing an item onto a stack

Figure 6.6: The final stepin pushing

What if the stack is empty when you try to push an item? In that case, siTop will be Nothing when you execute the following code:

Set siNewTop.NextItem = siTop

The new node's NextItem property will point to Nothing, as it should. Executing the final line of code:

Set siTop = siNewTop

causes the top of the stack to point to this new node, which then points to Nothing. It works just as it should!

Popping Items from the Stack

Popping an item from the stack removes it from the stack and makes the top pointer refer to the new item on the top of the stack. In addition, in this implementation, the Pop method returns the value that was just popped.

The code for the Pop method, as shown in Listing 6.3, follows these steps:

  1. Makes sure there's something in the stack. (If not, Pop doesn't do anything and returns a null value.)

  2. Sets the return value of the function to the value of the top item.

  3. Makes the stack top point at whatever the first item is currently pointing to. This effectively removes the first item in the stack.

Listing 6.3: Use the Pop Method to Remove an Item from the Stack

Public Function Pop() As Variant
    If Not StackEmpty Then
        ' Get the value from the current top stack element.
        ' Then, get a reference to the new stack top.
        Pop = siTop.Value
        Set siTop = siTop.NextItem
    End If
End Function

What happens to the node that used to be at the top of the stack? Once there are no more references to an instance of a class module, VBA can remove that instance from memory, effectively “killing” it. If you're not convinced, add a Debug.Print statement to the Terminate event procedure for the StackItem class. You'll see that VBA kills off unneeded objects as soon as there are no more references to the object.

The diagram in Figure 6.7 demonstrates the tricky step: popping an item from the stack. The code causes the stack pointer, siTop, to refer to the item to which siTop previously referred. That is, it links around the current top item in the stack. Once that occurs, there's no reference to the current top item, and VBA can “kill” the item.

Is the Stack Empty?

You may need to be able to detect whether the stack is currently empty. To make that possible, the example implementation of the Stack data structure provides a read-only StackEmpty property. Providing the information is simple: if siTop is currently Nothing, the stack must be empty.

Property Get StackEmpty() As Boolean
    ' Is the stack empty?  It can
    ' only be empty if siTop is Nothing.
    StackEmpty = (siTop Is Nothing)
End Property

Figure 6.7: Link around the top node to pop an item from the stack.

Given this property, you can write code that pops items until the stack is empty, like this:

Do While Not stk.StackEmpty
    Debug.Print stk.Pop()
Loop

What's on Top?

You may need to know what's on the top of the stack without removing the item. To make that possible, the example implementation of the Stack data structure includes a read-only StackTop property that returns the value of the item to which siTop points (or Null, if siTop is Nothing):

Property Get StackTop() As Variant
    If StackEmpty Then
        StackTop = Null
    Else
        StackTop = siTop.Value
    End If
End Property

A Simple Example

Listing 6.4 shows a few examples using a stack data structure. The first example pushes a number of text strings onto a stack and then pops the stack until it's empty, printing the text to the Debug window. The second example calls a series of procedures, each of which pushes its name onto the stack on the way in and pops it off on the way out. The screen in Figure 6.8 shows the Debug window after running the sample.

Listing 6.4: Using the Stack Data Structure

Dim stkTest As New Stack
Sub TestStacks()
    ' Push some items, and then pop them.
    stkTest.Push ""Hello"
    stkTest.Push "There"
    stkTest.Push "How"
    stkTest.Push "Are"
    stkTest.Push "You"
    Do While Not stkTest.StackEmpty
        Debug.Print stkTest.Pop()
    Loop
    ' Now, call a bunch of procedures.
    ' For each procedure, push the proc name
    ' at the beginning, and pop it on the way out.
    Debug.Print
    Debug.Print "Testing Procs:"
    stkTest.Push "Main"
    Debug.Print stkTest.StackTop
    Call A
    Debug.Print stkTest.Pop
End Sub
Sub A()
    stkTest.Push "A"
    Debug.Print stkTest.StackTop
    Call B
    Debug.Print stkTest.Pop
End Sub
Sub B()
    stkTest.Push "B"
    Debug.Print stkTest.StackTop
    Call C
    Debug.Print stkTest.Pop
End Sub
Sub C()
    stkTest.Push "C"
    Debug.Print stkTest.StackTop
    ' You'd probably do something in here...
    Debug.Print stkTest.Pop
End Sub

Figure 6.8: Debug window after the stack example has run

© 1997 by SYBEX Inc. All rights reserved.