The stack data structure is a collection of items that supports “last in, first out” access. You have two operations: “Push” an item onto the stack, and “Pop” to retrieve and remove the most recently added item. It’s like the stack of plates in a buffet restaurant, where unless you’re a rule-breaking savage, you can only take the plate on top, which was added last.
Compare to a queue, where when you get a value from it, you’re getting the oldest thing it contains.
A stack is used by the system to hold local variables and your position in the code when making multiple levels of calls in a program. Variables defined in the current module are at the top of the stack, then when you exit the module you “pop” that off, discarding it, so you have access to the calling function’s local variables again.
As such, creating your own stack data structure is often useful for “flattening” recursive functions. Rather than calling itself, the function can push onto its stack whatever state information it needs to retain, go do the other thing, then pop its previous data off the stack and resume. This lets you bypass the limitations of your execution environment’s stack (for maximum depth of function calls, for instance), and can be more efficient.
Specification
The Stack class I present here has these properties and methods:
- Size As Long: the number of entries in the stack.
- IsEmpty As Boolean: True if the stack contains no entries (same as stack.Size = 0).
- Sub Push(value): Add a value to the stack.
- Function Pop As Variant: Remove the most recently added element and return its value. If the stack is empty, returns EMPTY.
- Function Peek As Variant: Returns the value of the most recently added element, but without removing it from the stack. If the stack is empty, returns EMPTY.
Implementation notes
Like the Queue class in the previous post, this class uses a helper class, StackNode, to contain the value property of the element and a pointer to the next node, if any. This is an even simpler implementation because it only needs to keep track of one end of the list of elements — the most recent one. When an element is added, it becomes the new top element and the new element’s Next pointer points to the previous top element.
In the above example, the stack was populated with the elements A, B, and C. When the caller starts “popping” those values, they’re returned in reverse order.
In the Queue class, to make it more versatile for handling objects versus whatever, there’s a way to specify what value to return if the queue is empty. Arbitrarily, I didn’t do that for Stack. Pop always returns EMPTY if the stack has nothing in it. This is inconvenient if the stack contains objects because you don’t know whether to use Set on the assignment. Just don’t be lazy — test IsEmpty before popping.
You could also create a child class that only supports objects, leveraging most of this code, and have it return Nothing if the stack is empty — that way a Set statement always works with Pop. I’ll discuss class inheritance and method overriding in a later post.
If you find this website helpful and want to give back, may I suggest buying, reading, and reviewing one of my excellent books? More are coming soon!
If you want email whenever there’s a new post, you can subscribe to the email list, which is 100% private and used only to send you information about stuff on this site.
Source
Private Class StackNode Public value As Variant Public Next As StackNode Sub New(value) If IsObject(value) Then Set me.value = value Else me.value = value End Sub End Class%REM Class Stack By Andre Guirard Description: Implementation of the classic Stack data structure. Constructor: New Stack %END REMClass Stack Private z_top As StackNode Private z_count As Long%REM Property Get Size Description: Number of elements in the stack %END REMPublic Property Get Size As Long Size = z_count End Property%REM Property Get IsEmpty Description: TRUE if there are no elements in the stack. %END REMPublic Property Get IsEmpty As Boolean me.IsEmpty = (z_top Is Nothing) End Property%REM Sub Push Description: Add a value to top of stack %END REMSub Push(value) Dim nod As New StackNode(value) Set nod.Next = z_top Set z_top = nod z_count = z_count + 1 End Sub%REM Function Pop Description: Remove top value from stack and return it. %END REMFunction Pop As Variant Dim nod As StackNode If z_count Then z_count = z_count - 1 If IsObject(z_top.value) Then Set Pop = z_top.value Else Pop = z_top.value Set nod = z_top Set z_top = z_top.next Delete nod End If End Function%REM Function Peek Description: Return top value from stack without removing it. %END REMFunction Peek As Variant If z_count Then If IsObject(z_top.value) Then Set Peek = z_top.value Else Peek = z_top.value End If End Function Sub Delete Dim nod As StackNode Do Until z_top Is Nothing Set nod = z_top.Next Delete z_top Set z_top = nod Loop End Sub End Class
Example code
FileSearch revised
For starters, I’d like to revisit the FileSearch example from the Queue class. You may recall there was a problem with it as regards the order in which it scanned the folders. The ordering imposed by the Queue class made the scan breadth-first rather than depth-first — the siblings of a folder were scanned before its descendants. This makes the list of resulting paths come out in an order most people would find undesirable.
If you instead use a Stack object to track your work, this lends itself well to a depth-first traversal of the folder tree. Anything you add to the stack is at the top, so it’ll be the next thing you pull off. So as you process a folder and “push” its subfolders, the subfolders will be processed next, as we desire.
There is still one little problem though. Dir$ gives us folder contents in alphabetical order, and if we push them all onto the work stack in that order, when we pull them off they’ll be reversed. The matches in a folder will still be immediately followed by matches in its subfolders, but the list will not be alphabetical — matches in /foods/vegetables will appear before matches in /foods/meat.
You might decide this is acceptable, and for many functions it doesn’t really matter what order the work gets done so long as it all gets done. But in this case let’s make it nice — let’s have the output in an order a human would like best.
To make it work, the updated FileSearch function doesn’t put subfolder names directly onto the work stack when it sees them. Instead it pushes them onto a second stack, reverser. After it’s done scanning the folder, it shifts the entries from reverser onto the work stack. As its name suggests, the purpose of reverser is to reverse the order of the subfolder names so the last one added to work is the first in alphabetical order.
%REM Function FileSearch Description: Recursively search a given folder for files who name match a set of patterns. Works on any OS. Arguments: baseDir: the folder you want to search. May optionally have a directory delimiter at the end, e.g. "C:\foo" or "C:\foo\". Should work on any OS. patterns: a string delimited with "|" listing the second operands for a LIKE operator to match against the filename, case insensitive. E.g. "*.dat|ac[0-5]*.cab" to find all ".DAT" files and all ".CAB" files whose names begin "ac" followed by digit 0 to 5. Returns: array of strings containing full filepaths of all matching files, or if no matches found, array containing one blank element. %END REMFunction FileSearch(ByVal baseDir$, ByVal patterns$) As Variant Dim delim$, afile$, results$, adir$, patternarr Dim work As New Stack Dim reverser As New Stack' used to reverse a list of stringsDim files List As Boolean' find what path delimiter the caller prefers.If basedir Like "/*" Then delim = "/" ' linux style path ElseIf basedir Like "\*" Or basedir Like "[A-Z]:\*" Then delim = "\" ' windows style path Else Error 20030, "FileSearch needs an absolute filepath." End If patternarr = Split(LCase(patterns), "|")' internally we want all filepaths to end with the folder separatorIf baseDir Like "*[!\/]" Then baseDir = baseDir & delim work.push basedir' while there are directories in the queue, process the first directory.Do Until work.IsEmpty adir = work.Pop Erase files afile = Dir$(aDir & "*", Attr_hidden + Attr_system) ' all files but not directories. Do Until afile = "" files(afile) = True' remember the names of the filesIf IsLikeAnyOf(LCase(aFile), patternarr) Then results = results & NEWLINE & adir & afile End If afile = Dir$ Loop' now find the names of each subfolder.afile = Dir$(aDir, Attr_directory + attr_hidden)' this will include files alsoDo Until afile = "" If afile <> "." And afile <> ".." Then If Not IsElement(files(afile)) Then ' this is a folder. Save its name to add to the work list. Call reverser.Push(afile) End If End If afile = Dir$ Loop' if any subfolders were found, queue them for processing next.Do Until reverser.IsEmpty Call work.Push(aDir & reverser.Pop & delim) Loop Loop FileSearch = Split(Mid$(results, 2), NEWLINE) End Function
Obviously a stack object isn’t the only way to process a list of strings in reverse order, but since this is a demo I thought it’d be cool to do it that way.
Postfix expression evaluator
An arithmetic expression in postfix notation has the operands preceding the operator, e.g. “2 3 +” rather than “2 + 3”. An advantage of postfix is that it doesn’t require parenthesis to group things — the operator order is implicit in the order in which you arrange the terms. For instance, “4 2 3 + /” means first add 2 and 3, then divide 4 by that (= 0.8).
A stack is ideal for evaluating such an expression, because you have to accumulate operands until you find out what to do with them, and when you hit the operator, it operates on the most recently encountered two operands, and the result goes back on the stack to be available for further operations. For instance, to evaluate “1 2 3 + + 8 5 – /”, here’s how the stack looks as we process each token:
| Token | Evaluation stack |
| 1 | 1 |
| 2 | 2 1 |
| 3 | 3 2 1 |
| + | 5 1 |
| + | 6 |
| 8 | 8 6 |
| 5 | 5 8 6 |
| – | 3 6 |
| / | 2 |
The code to do this evaluation is surprisingly simple.
%REM Function PostfixEval Description: Evaluate a mathematical expression in postfix syntax. Tokens are delimited by spaces, e.g. "2 3 +" %END REMFunction PostfixEval(expr$) As Double Dim operands As New Stack Dim op1 As Double, op2 As Double, result As Double Dim tokenarr tokenarr = FullTrim(Split(expr, " ")) ForAll token In tokenarr If IsNumeric(token) Then operands.Push CDbl(token) ElseIf token Like "[-+*/]" And operands.Size > 1 Then' an operator, and there are enough operands to evaluate itop2 = operands.Pop op1 = operands.Pop Select Case token Case "+" result = op1 + op2 Case "-" result = op1 - op2 Case "*" result = op1 * op2 Case "/" result = op1 / op2 End Select operands.Push result Else Error 20030, "Invalid postfix syntax" End If End ForAll If operands.Size <> 1 Then' not enough operators to use up all the operands.Error 20030, "Invalid postfix syntax" End If PostfixEval = operands.Pop End Function
Final thoughts
There are other ways to implement the functionality of a stack besides that given here. Behind the scenes it could use an array instead of a singly linked list (if you don’t mind the size limit). It could leverage the LinkedList class I plan to discuss in a future post, which is ridiculously overqualified for the purpose of managing a stack but you don’t have to use all its functions.
This is just the minimal general-purpose implementation that doesn’t rely on other classes.
Appendix 1: The Mikle Stack
A comment below about an alternate implementation led me to try out that option. Here’s the code for a stack implementation with the same methods, but based on a List data structure rather than a linked list.
%REM Class MikleStack By Mikle Description: Implementation of the classic Stack data structure using a List Constructor: New MikleStack %END REMClass MikleStack Private z_stak List As Variant Private z_count As Long%REM Property Get Size Description: Number of elements in the stack %END REMPublic Property Get Size As Long Size = z_count End Property%REM Property IsEmpty (read-only) Description: TRUE if there are no elements in the stack. %END REMPublic Property Get IsEmpty As Boolean me.IsEmpty = (z_count = 0) End Property%REM Sub Push Description: Add a value to top of stack %END REMSub Push(value) z_count = z_count + 1 If IsObject(value) Then Set z_stak(z_count) = value Else z_stak(z_count) = value End Sub%REM Function Pop Description: Remove top value from stack and return it. %END REMFunction Pop As Variant If z_count Then Dim key$ key$ = z_count If IsObject(z_stak(key)) Then Set Pop = z_stak(key) Else Pop = z_stak(key) Erase z_stak(key)' so if it's an object there's not an unnecessary reference to it from here.z_count = z_count - 1 End If End Function%REM Function Peek Description: Return top value from stack without removing it. %END REMFunction Peek As Variant If z_count Then Dim key$ key$ = z_count If IsObject(z_stak(key)) Then Set Peek = z_stak(key) Else Peek = z_stak(key) z_count = z_count - 1 End If End Function End Class
stack class :
Why not this :
Function Pop As Variant
Dim nod As StackNode
Set nod = z_top
Set z_top = nod.Next
Delete nod
z_count = z_count – 1
pop = me.peek()
End Function
Sub Delete
Do Until z_top Is Nothing
me.pop
Loop
End Sub
I prefer to have Pop return EMPTY rather than throw an “Object variable not set” error when the stack is empty.
It’s true the Delete routine is more complicated than it needs to be — I wanted the better performance of not having to return all the values.
However, given that there are no reference loops in this data structure, we could also just not have a Delete sub. Regular garbage collection should handle this case.
The implementation is classic from the tutorial, but it looks too complicated for lotusScript. How about a class that has a list and a counter? List is а very powerful tool, this stuff is stronger than Goethe’s “Faust”!
something like this:
class stackSimple
private counter as long, values list of variant
sub push(newVal)
values(counter++) = newVal
end sub
function pop
if( counter )then pop= values(counter) else pop= empty:exit function
erase values(counter)
counter–
end function
I did the Mikle version with the same checks and comments and it’s 8 lines shorter, so that’s good. Of course then it’s not the linked-list example I wanted. 🙂
I’ll include the shorter version above also. Thanks Mikle!