Stacks

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.

[Graphics:../Images/index_gr_45.gif]

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

[Graphics:../Images/index_gr_46.gif]
[Graphics:../Images/index_gr_47.gif]

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

[Graphics:../Images/index_gr_48.gif]
[Graphics:../Images/index_gr_49.gif]
[Graphics:../Images/index_gr_50.gif]
[Graphics:../Images/index_gr_51.gif]
[Graphics:../Images/index_gr_52.gif]
[Graphics:../Images/index_gr_53.gif]
[Graphics:../Images/index_gr_54.gif]

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.

[Graphics:../Images/index_gr_55.gif]
[Graphics:../Images/index_gr_56.gif]
[Graphics:../Images/index_gr_57.gif]
[Graphics:../Images/index_gr_58.gif]
[Graphics:../Images/index_gr_59.gif]
[Graphics:../Images/index_gr_60.gif]

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.