by Kevin Bradley
Most computer science classes at some point talk about types of data storage. How data is stored is often as important as the data itself. An example of that is the simple stack.
Stacks are used in computing for many things at many different levels within a computer. Stacks are used by some hardware microprocessors to store data that is being worked with. Operating systems use stacks to store subroutine variables. And application programs can use stacks to keep track of objects it is working with.
The idea of a stack is that the last item put on the stack is the first item used. When might you want to do this? For example, in the puzzle “Tower of Hanoi,” you have 3 “stacks” of disks and move the disks around from stack to stack. But since the only disk you can move is the top disk, you are essentially moving the last disk that was placed on that stack. Another example might be when you need to list something in reverse order. You would put each item on the stack and then pull them from the stack, resulting in a reversal of the original order.
This “last-in, first-out” method is often referred to as “LIFO.” There are other methods that can be used for data structures, but not for stacks. Queues, for example, use “first-in, first-out” or “FIFO” methods.
AppleScript doesn’t provide support for stacks natively, but the list type can be used to create a stack. Items in an AppleScript list can be almost any data type, which helps to make our implementation of a stack data type usable for a great variety of purposes.
Building a Library for Stacks
There are a small handful of operations that you can do with a stack, and so only a few handlers that we need to write:
First, let’s create a stack object. For this article, I’m using the sortlib from my Nite Flite script library. So we are going to collect these scripts into one and save them as a library for use in another script that exercises the stack. This gives us a reusable version of the stack implementation that we can use for any purpose we might need. We’ll also define a property called stackResult that will contain the results of some of our stack operations. Both objects are defined as list objects:
property newstack : {}
property stackResult : {}
We will need a way to determine whether the stack is empty or not. Some implementations also give you the ability to find out how many items are on the stack. But since AppleScript’s count and length keywords let us get that number, we will content ourselves with a simple IsEmpty boolean test:
on stackIsEmpty(theStack) -- copy this to the first one.
--returns true if stack is empty, else false
if length of theStack is 0 then return true
return false
end stackIsEmpty
Next, we need a way to add something to the stack. If we visualize the stack as a stack of plates, we need the ability to “push” a new plate onto the stack. Since we’re creating a self-contained script library object, we’ll pass in the stack and the item to be pushed:
on Push(theStack, theData) -- copy this to the first two
--returns the stack with the added item
set beginning of theStack to theData
return theStack
end Push
Next, we need a way take the first plate off of the stack. Most implementations call this operation “pop,” though some use the word “pull.” For our purposes, we will use pop, since it is more often used:
on Pop(theStack) -- again copy to the script we're building
--returns the new stack
--stackResult contains the popped item
--trying to Pop an empty stack results
--in stackResult being undefined (anything)
if stackIsEmpty(theStack) then
set stackResult to anything
return {}
else
set stackResult to item 1 of theStack
return (rest of theStack)
end if
end Pop
Note that stackResult can be undefined if you call Pop with nothing in the stack. Be sure to test for stack emptiness before you try to Pop something!
There will be times when you may want to know what the top item is without removing it from the stack. This kind of operation is generally called a “look ahead” in computer science, and in the language of stacks, this is usually called “peek” or “top.” Again, we’ll use peek since it is more common:
on Peek(theStack) -- the final entry.
--return first item if stack is not empty
if stackIsEmpty(theStack) then
--set stack result to false to indicate we didn't get anything
set stackResult to false
return {}
else
--set stack result to true, we got a value!
set stackResult to true
return item 1 of theStack
end if
end Peek
We now have a complete implementation of a stack! Collect these scripts together in one script document if you haven’t been doing so all along and save the collected script in a new folder in your user’s Scripts folder called “Script Library”. Name the script itself “StackLib” so we can refer to it later and save it as a script (so the file will be named “StackLib.scpt” in the new folder after you save it).
Using Our Library
The list data type of AppleScript makes this an easy bit of code to write. We can now use the stack in our program. Here’s a simple program that pushes the numbers from 1 to 5 and then pops them in reverse order:
--load the library
set scriptPath to (path to scripts folder from user domain) & "Script Library:"
set stackLib to load script ((scriptPath as text) & "stackLib.scpt") as alias
--create a new stack
copy stackLib's newstack to myStack
--load the stack
repeat with myValue from 1 to 5
display dialog "Push " & myValue
set myStack to stackLib's Push(myStack, myValue)
end repeat
--unload: notice the values are in reverse (lifo) order!
repeat while not (stackLib's stackIsEmpty(myStack))
set myStack to stackLib's Pop(myStack)
set myResult to stackLib's stackResult
display dialog "Pop " & myResult
end repeat
See if you can find a use for stacks in something you write. Next article we’ll cover queues. Happy scripting!