FB Data Structures: Array Stack

[rdc]

This version of the stack object is based on a static array. Since the array is static, the stack size is limited to the size of the array. In applications where you might be working with a fixed number of quantities, using an array is an efficient efficient way to implement a stack. If you are working with an unknown amount of quantities, using a dynamic method for creating the stack is the better approach.

Stack Object Code

Code: [Select]

/'****************************************************************************
*
* Name: fbstack.bi
*
* Synopsis: A stack object for FB programs.
*
* Description: This program implements a stack object for use in FB programs.
*
* Copyright 2010, Richard D. Clark
*
*                          The Wide Open License (WOL)
*
* Permission to use, copy, modify, distribute and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice and this license appear in all source copies.
* THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY OF
* ANY KIND. See http://www.dspguru.com/wol.htm for more information.
*
*****************************************************************************'/

'Put the stack within a namespace.
Namespace fbStackarr

'Include the standard data object.
#Include "dataobj.bi"

'Define True/False values.
#Ifndef FALSE
#Define FALSE 0
   #Define TRUE (Not FALSE)
#EndIf

'Stack error codes.
Enum stackerror
stacknoerror = 0
stackempty
stackfull
End Enum

'Stack object definiton.
Type stackobj
Private:
_stack (0 To 10) As dataobj 'The actual stack. The 0 index is used as the empty flag.
_cnt As Integer 'The number of items in the stack.
_lasterror As stackerror 'The last error.
Declare Sub _ClearStack() 'Clears the stack, setting each element to NULL.
Public:
Declare Constructor ()
Declare Destructor ()
Declare Sub ClearStack () 'Calls _ClearStack.
Declare Function Count() As Integer 'Number of items on the stack.
Declare Function StackSize () As Integer 'Returns the size of the stack, i.e. the upper bounds.
Declare Function Push (dt As dataobj) As Integer 'Pushes an item onto stack. Returns True/False.
Declare function Pop (dt As dataobj) As Integer 'Retrieves a data obj from stack. Returns True/False.
Declare Function GetLastError () As stackerror 'Returns the last error code.
Declare Function GetErrorMessage (e As stackerror) As String 'Returns the error as a string.
End Type

'Deallocate the stack.
Sub stackobj._ClearStack ()
'Clear each data object in stack.
For i As Integer = 0 To UBound(_stack)
_stack(i).ClearData
Next
'Set the number of items to zero.
_cnt = 0
End Sub

'Constructor
Constructor stackobj ()
'Clear stack data.
_ClearStack
'Set default error.
_lasterror = stacknoerror
End Constructor

'Destructor
Destructor stackobj ()
_ClearStack
End Destructor

'Clears stack.
Sub stackobj.ClearStack ()
_ClearStack
End Sub

'Returns the number of items on the stack or 0 if empty.
Function stackobj.Count () As Integer
Return _cnt
End Function

'Returns the size of the stack, i.e. the upper bounds. Lower bound is always 1.
Function stackobj.StackSize () As Integer
Return UBound(_stack)
End Function

'Pushes an item onto the stack. Returns True if successful, False if an error occured.
Function stackobj.Push (dt As dataobj) As Integer
Dim ret As Integer = TRUE

'Set the default error code.
_lasterror = stacknoerror
'Is the stack full?
If _cnt = UBound(_stack) Then
ret = FALSE
_lasterror = stackfull
Else
'Add the new element to the stack.
_cnt += 1
_stack(_cnt) = dt
EndIf

Return ret
End Function

'Pops an item from the stack. If stack is empty returns False, else True is returned.
Function stackobj.Pop (dt As dataobj) As Integer
Dim ret As Integer = TRUE

'Set the default error code.
_lasterror = stacknoerror
'Nothing on the stack.
If _cnt = 0 Then
ret = FALSE
_lasterror = stackempty
Else
'Return the top item.
dt = _stack(_cnt)
'Set the item to NULL.
_stack(_cnt).ClearData
_cnt -= 1
EndIf

Return ret

End Function

'Returns the last error code.
Function stackobj.GetLastError () As stackerror
Return _lasterror
End Function

'Returns the error as a string.
Function stackobj.GetErrorMessage (e As stackerror) As String
Dim ret As String

Select Case e
Case stacknoerror
ret = "Stack: No error"
Case stackempty
ret = "Stack: Stack empty"
Case stackfull
ret = "Stack: Stack full"
Case Else
ret = "Stack: Unknown error code"
End Select

Return ret
End Function

End Namespace


Code Review

Code: [Select]

Namespace fbStackarr
The stack object is placed within a namespace to prevent any naming conflicts that might appear in the code. The namespace identifies which stack object we are using, namely the array-based stack object.

Code: [Select]

'Include the standard data object.
#Include "dataobj.bi"

This is the standard data object that all of the various data structures use. The data object provides variant-like data access for each data structure.

Code: [Select]

'Define True/False values.
#Ifndef FALSE
   #Define FALSE 0
   #Define TRUE (Not FALSE)
#EndIf

A simple True/False define. The defines are wrapped within an #Ifndef in case the True/False have already been defined in some other code.

Code: [Select]

'Stack error codes.
Enum stackerror
    stacknoerror = 0
    stackempty
    stackfull
End Enum

These are the error codes that the stack can generate. If a function returns False, you can check the GetLastError function to get the error code and GetErrorMessage to get a text version of the error code. Both versions of the stack can generate the stackempty error code. However, only the array-based version can generate the stackfull error code since we are working with a static array. The stacknoerror is an important error code. It defines the "no error" condition, and is used as the default error code for each of the functions.

Private Data

The private data of the stack object is only accessible from within the stack object itself. This ensures that the data of the object is hidden behind the Public interface and ensures that the object maintains data integrity.

Code: [Select]

_stack (0 To 10) As dataobj 'The actual stack. The 0 index is used as the empty flag.

The stack itself is contained within the array. Notice that even though the stack has a lower bound of 0 the stack actually can only contain 10 values, 1 through 10. The 0 index is called a signal index, and is used to signal that the stack is empty. Using signal values is a common technique in array based applications, and simplifies the code.

Code: [Select]

_cnt As Integer 'The number of items in the stack.

This is the number of items currently within the stack and represents the Top of the stack. This value will range from 0, an empty stack, to the upper bounds of the array, 10 in this case. Since this represents the Top of the stack, this value is used to index into the stack array.

Code: [Select]

_lasterror As stackerror 'The last error.

Whenever a method of the object is invoked, this variable is set to the default error code stacknoerror. If an error occurs with a particular method, this variable will contain the error code.

Private Methods

Code: [Select]

'Clear the stack.
Sub stackobj._ClearStack ()
    'Clear each data object in stack.
    For i As Integer = 0 To UBound(_stack)
        _stack(i).ClearData
    Next
    'Set the number of items to zero.
    _cnt = 0
End Sub

This private method clears the stack; that is, it iterates through the array and sets each data object to the default value of NULL. Since the stack does not contain any valid data at this point, cnt is set to 0 indicating an empty stack.

As you will see, there is more than one place where we will want to clear the stack. Rather than writing duplicate code, a single subroutine is created that can be called from all the other methods as needed. This reduces the chances of an bug creeping into the code, and simplifies the maintenance of the object.

Public Methods

The public methods comprise the public interface to the object. This is how the rest of the code can interact with the object. The public interface controls access to the object, ensuring that we maintain data integrity within the object.

Code: [Select]

'Constructor
Constructor stackobj ()
    'Clear stack data.
    _ClearStack
    'Set default error.
    _lasterror = stacknoerror
End Constructor

The object constructor is called when the object is created. The stack is cleared within the Constructor so that we know we have a clean stack to work with from the beginning. While in some cases this might not be necessary, the "this can never happen" does indeed never happen here since we take the precaution to ensure a good starting point. The Constructor also sets the default error code, again just to make sure that we are working with good data right from the start.

Code: [Select]

'Destructor
Destructor stackobj ()
    _ClearStack
End Destructor

The destructor is called when the object goes out of scope, and again the stack is cleared. Here it is necessary to clear the stack since the data object supports string values and strings are dynamically allocated within the data object. It is important to release any memory that the data object may have allocated before we exit the object.

Code: [Select]

'Clears stack.
Sub stackobj.ClearStack ()
    _ClearStack
End Sub

Again, we have an instance of clearing the stack, this time by the user code. By offering a way to clear the stack within the public interface, the stack can be reused for different values without having to create multiple objects. This is why the stack object uses the data object; to allow the user the flexibility to place different values on the stack as needed without having to recode the object for different values.

Code: [Select]

'Returns the number of items on the stack or 0 if empty.
Function stackobj.Count () As Integer
    Return _cnt
End Function

This function simply returns the current stack count. Again, this represents the top of the stack.

Code: [Select]

'Returns the size of the stack, i.e. the upper bounds. Lower bound is always 1.
Function stackobj.StackSize () As Integer
  Return UBound(_stack)
End Function

This function returns the size of the stack, that is the upper bound of the stack array. This is useful for determining how many items can fit within the stack and for iterating through the stack.

Code: [Select]

'Pushes an item onto the stack. Returns True if successful, False if an error occured.
Function stackobj.Push (dt As dataobj) As Integer
    Dim ret As Integer = TRUE

    'Set the default error code.
    _lasterror = stacknoerror
    'Is the stack full?
    If _cnt = UBound(_stack) Then
        ret = FALSE
        _lasterror = stackfull
    Else
        'Add the new element to the stack.
        _cnt += 1
        _stack(_cnt) = dt
    EndIf

    Return ret
End Function

Here is the Push method of the stack, the way we get data into the stack. The function returns True if all went well, False if an error occurs. For an array-based stack we need to make sure that the Push does not exceed the array's upper bound, so that is checked with the UBound command. If the Push would exceed the array limit, we do nothing and set the error code. Here you can see how the cnt value acts as the Top indicator of the stack. If the cnt is equal to the upper bounds of the array, the stack is full.

If we still have room in the stack, then we increment the cnt variable, move the Top by one, and set the data object at the cnt index to the value of the passed data object.

Code: [Select]

'Pops an item from the stack. If stack is empty returns False, else True is returned.
Function stackobj.Pop (dt As dataobj) As Integer
    Dim ret As Integer = TRUE

    'Set the default error code.
    _lasterror = stacknoerror
    'Nothing on the stack.
    If _cnt = 0 Then
        ret = FALSE
        _lasterror = stackempty
    Else
        'Return the top item.
        dt = _stack(_cnt)
        'Set the item to NULL.
        _stack(_cnt).ClearData
        _cnt -= 1
    EndIf

    Return ret
End Function

The Pop function will remove an item from the stack and place in the data object parameter. Here you see the signal value in action. If the cnt is 0, that is pointing to the 0 index of the array, the stack is empty. While we are wasting one index value in the array, the implementation is clean, simple and easy to understand. Well worth wasting an array index.

When an item is removed from the stack, the array data object's ClearData at the _cnt index location is called before the count is decremented. This ensures that the stack does contain any strange data and that all unused positions within the stack array have consistent values. Again, this may seem a bit of overkill, but this covers things we may not know at the moment. It is better to do a little defensive programming now, rather than trying to find an strange bug later on.

Code: [Select]

'Returns the last error code.
Function stackobj.GetLastError () As stackerror
    Return _lasterror
End Function

'Returns the error as a string.
Function stackobj.GetErrorMessage (e As stackerror) As String
    Dim ret As String

    Select Case e
        Case stacknoerror
            ret = "Stack: No error"
Case stackempty
            ret = "Stack: Stack empty"
        Case stackfull
           ret = "Stack: Stack full"
        Case Else
   ret = "Stack: Unknown error code"
    End Select

    Return ret
End Function

The last two functions return the last error code and the error text for an error code. Providing human-readable error codes makes the programmer's job a little easier and can be used to display meaningful error messages to the user. "Stack empty" is a lot more meaningful than Error code 1.

Test program

Code: [Select]

/'****************************************************************************
*
* Name: teststack.bas
*
* Synopsis: A test program for the array stack object.
*
* Description: This program excersises the members of the stack object.
*
* Copyright 2010, Richard D. Clark
*
*                          The Wide Open License (WOL)
*
* Permission to use, copy, modify, distribute and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice and this license appear in all source copies.
* THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY OF
* ANY KIND. See http://www.dspguru.com/wol.htm for more information.
*
*****************************************************************************'/

#Include "fbstack.bi"

Dim myStack As fbStackarr.stackobj
Dim myData As fbstackarr.dataobj
Dim As Integer ret, i, ss, dt
Dim As fbStackarr.stackerror serror
'Add some integers to the stack.
ss = myStack.StackSize
'Will generate an error with last items since number of items is greater than stack size.
For i = 1 To ss + 1
    myData = i
    ret = myStack.Push(myData)
    If ret = FALSE Then
        serror = myStack.GetLastError
        Print "Error code: " & serror & ". " & myStack.GetErrorMessage(serror) & "."
        Exit For
    Else
        Print "Added " & i & " to the stack."
    EndIf
Next
Print
'How many items on the stack.
ss = myStack.Count
Print "There are " & ss & " items on the stack."
Print
'Will generate an error on last item since stack will be empty.
Do While myStack.Count > -1
    ret = myStack.Pop(myData)
    If ret = FALSE Then
        serror = myStack.GetLastError
        Print "Error code: " & serror & ". " & myStack.GetErrorMessage(serror) & "."
        Exit Do
    Else
       dt = myData
       Print "Popped " & dt & " from the stack."
    EndIf
Loop
Print
Print "Stack count: " & myStack.Count & "."
Sleep

The test program tests the methods of the object as as well as the edge conditions; that is, what happens if you Push too many items or Pop too many items? It is important to test edge conditions to make sure the object behaves properly. If you don't you can be sure your users will eventually test them for you.

Program Output

Added 1 to the stack.
Added 2 to the stack.
Added 3 to the stack.
Added 4 to the stack.
Added 5 to the stack.
Added 6 to the stack.
Added 7 to the stack.
Added 8 to the stack.
Added 9 to the stack.
Added 10 to the stack.
Error code: 2. Stack: Stack full.

There are 10 items on the stack.

Popped 10 from the stack.
Popped 9 from the stack.
Popped 8 from the stack.
Popped 7 from the stack.
Popped 6 from the stack.
Popped 5 from the stack.
Popped 4 from the stack.
Popped 3 from the stack.
Popped 2 from the stack.
Popped 1 from the stack.
Error code: 1. Stack: Stack empty.
Stack count: 0.

Here we see the output of the test program. Notice that the object generated the proper error codes in the proper places (and didn't crash), even though an error was generated within the system. It is important to handle errors gracefully, and if possible, continue to operate normally even after an error has been encountered. If the program can't continue, then the program should exit gratefully after cleaning up any open resources. Your user will greatly appreciate the fact that you took the time to make sure the program behaves well, even in adverse conditions.

Code Download

You can download the FreeBasic code and FBEdit projects at: http://cid-bcdbe1b9697ff5dc.skydrive.live.com/browse.aspx/.Public/FBData Look for stack.zip in the folder.

[Jim]

When an item is removed from the stack, the array data object's ClearData at the _cnt index location is called before the count is decremented. This ensures that the stack does contain any strange data and that all unused positions within the stack array have consistent values. Again, this may seem a bit of overkill, but this covers things we may not know at the moment. It is better to do a little defensive programming now, rather than trying to find an strange bug later on.

I think it's good practice too.  This is defensive coding in FB, but if you were using a garbage collecting language like C# or Java then if you did not 'let go' of the popped stack entries it would lead to a memory leak, the objects in the stack would hang around until the entries were overwritten by another push or the stack itself was deleted.

Of course, you would use the built-in Stack classes that C# and Java support instead of building your own, but I have seen this kind of memory leak in real life.

Jim