An Introduction to Stacks by Seth Willits 10-21-03 Printer Version

Now, when you think of a stack you may think of a stack of papers, or a stack of dirty plates. Unless you've used some older programming languages or delt with the Classic Mac OS's System Stack in Pascal or C, you probably don't think of a data structure. Whether we're talking about programming or in life, a stack is an association of items such that the last item stored is the first item retrieved. With our dirty dishes, we remove the last plate from the table and place it on the top of the stack in the sink. Days later when we decide it's time to wash those dishes, the first plate we grab is the one from the top, the last one which was placed on the stack. We recognize this attribute of stacks and give it the caption "First in Last Out", or FILO. FIFOs on the other hand, (first in first out) are called "queues" but we won't be getting into those.

In programming, a stack is basically an array where there are two functions; one to add an item or "push" it on to the stack, and one to remove an item, or "pop" it. In REALbasic, there is no such thing as a "stack" or a Stack class, but instead, we can treat an array of any datatype as a stack by using the Append and Pop methods. (Pop was added to REALbasic 5.) When we want to push an item on to the stack, we call the Append method, and to retrieve it, we call Pop. If for instance we did this:

dim nums(-1), x as integer

nums.Append 1
nums.Append 2
nums.Append 3
nums.Append 4
nums.Append 5

When we use the the Pop method we get this:

x = nums.Pop // x = 5
x = nums.Pop // x = 4
x = nums.Pop // x = 3
x = nums.Pop // x = 2
x = nums.Pop // x = 1

As you can see, Pop not only retrieves the topmost item in the stack, it also removes it. It's important to remember this.

So when are stacks used? Stacks are most offen used in the place of recursion, which is where a function will call itself when some condition is met. A specific example where a stack is used is searching for a specific file in a given folder. Typically, a SearchFolder(filename as string, rootFolder as folderItem) as FolderItem method may be written which returns the folderitem for the file if it was found. SearchFolder would examine all of the items in the rootFolder, and if it comes across a folder within rootFolder, it would call itself again, passing the appropriate rootFolder.Item(n) as the rootFolder. This recursive method of searching is done all the time, not only for files, but also whenever any kind of tree-like heirarchial structure needs to be examined. However it does have some downsides. If you've used recursion before, you may have caused a StackOverflowException* by having too many levels of recursion (SearchFolder called itself too many times for REALbasic to handle). By using a stack, you can rid of this problem and actually pick up a little bit of a performance boost too.

* If you've never used recursion or don't know what a StackOverflowException is, don't worry about and pretend you never read that. While the "Stack" does refer to a stack of what we're talking about, you'll never receive a StackOverflowException when using a stack since the conceptual idea of a stack is used differently.

Using a Stack
The project for this tutorial is simply going to display a dialog to select a folder, and display all of the files inside of that folder, it's subfolder, their subfolders, and their subfolders, aaaalllll the way down to the deepest level. For example, if you selected the root folder on your hard drive, the project would a row to the listbox for every file on your hard drive. (By the way, don't do that. It'll take a very long time! :-)

The interface for the project is simply a listbox named "FilesList" and a pushbutton with the following code:

   dim folders(-1), rootFolder as FolderItem
   dim currentFolder, itemInFolder as FolderItem
   dim index, count as integer

   // Select Root Folder
   rootFolder = SelectFolder()
   if rootFolder = nil then return

     // Add rootFolder to stack
     folders.Append rootFolder

     // For each folder in the stack
     while UBound(Folders) > -1
       // Get the folder at the top of the stack
       currentFolder = folders.Pop

       // For each item in the current folder
       for index = currentFolder.Count DownTo 1
         itemInFolder = currentFolder.Item(index)
         if itemInFolder <> nil then

           // If item is a folder
           if itemInFolder.Directory = true then
             // Add folder to the stack
             folders.Append itemInFolder

           else
             // Add file to the listbox
             FilesList.AddRow itemInFolder.Name
           end if
          
       end if
     next
   wend


As you can follow from the comments, a dialog is displayed in which the user selects a folder. That folder then becomes the first item in the stack. The While-Wend loop then Pops each item in stack (one per iteration of the While loop) and then the For loop goes through each item inside of the folder that was popped from the stack. If and only if the itemInFolder is a folder itself, is it added to the stack. The only items ever in the stack are folder since only the folders need to be inspected.