Mathematica 9 is now available


Stacks are data structures with a top, wherein we remove the element most recently placed thereon; the descriptive phrase is "last in, first out," or LIFO for short. Stacks may be represented conveniently in Mathematica s nested lists. We push a new element onto the top by forming the nested list
newstack = {new,oldstack}.

One finds stack uses throughout computer science algorithms. For example they are extremely useful for walking through expression trees. We give a simple example below where we flatten an expression.

First we give simple Mathematica code to implement a stack.


Next we show a stripped-down Mathematica implementation of Flatten. It relies on recursion to flatten sublists and then joins the results.


Attempting to do this without an adequate $RecursionLimit setting can be hazardous to the health of your Mathematica session.


Next we show how to implement this without recursion. We initialize the length of our result to zero. We then walk through our expression left-to-right, depth first. Every element that is a list has its sub-elements pushed onto the main stack. Each non-list element gets put onto a secondary stack containing the result elements, and we increment the length of that result. When the main stack is empty we have put all non-list elements onto the secondary stack, so we simply pop off all elements therefrom and put them into a table.


It should be mentioned that this simple example illustrates a very common use of stacks, as a tool for algorithms that require walks through tree structures.