I'm looking for examples to give my students when lecturing about stacks, for use-cases of the stack in programming and life.
So far I've been thinking of a pole of rings (when you can insert or remove rings from the top).
My students are high school students I'm teaching next year for their matriculation exam. They have only some basic knowledge in procedural programming and the tip of the iceberg in Object-Oriented stuff.
Any ideas for more analogies or examples?
I once had to implement a limited undo function (undo changes to the current field, or addition/deletion of records).
The lists of undo deltas (one for field changes and one for records) were stored as stacks.
A stack of trays in a cafeteria. I also like the pole of rings analogy.
With the trays, you can pop (take a tray) and push (return it when you're done). You can see what the top tray (first item) is (ex. what color), and see if the stack is empty. Non-stack operations such as getting a count of the trays are non-trivial. It is also impossible to insert or remove a tray from a random position.
A rather interesting analogy is that of a firearms magazine.
if we look at this picture:
It is easy to see that bullets can be inserted from the top, and only the topmost bullet is accessible. Such is a stack. A magazine works by LIFO (Last In First Out), and so does a Stack.
Furthermore, the four (five1) basic operations of a Stack are applicable:
1The initializing of the stack isn't exactly a special operation a stack can do.
A stack is something used in programming when you need to keep a record of the history of versions. For example, many text editors use a stack data structure to save the changes made to the file. Also, revisions of posts on Stack Exchange have some form of a Stack (funny coincidence, isn't it?) to save the revisions (though I think the SE system uses partial functionality of a stack. I'll check that and edit this post when I have a definite answer about this particular part).
The very obvious usage of stack is, of course, the stack segment of computer memory. The call stack is, well, a call stack. (more on this can be seen here)
Another handy example is the browser back button. The browser has a stack with the links (technically, sort of cached versions) of pages you've been to. When pressing the "back" button, the stack's pop function is called, and you get redirected to that. When a link is pressed, a new element is pushed onto the stack.
The back button on a web browser is an excellent example of a stack implementation that is easily understood even by non-experts and easily demonstrated in a class. You can illustrate the stack in diagrams, and you can show it in action in a browser.
When a user visits a new web page, the current page gets pushed onto the stack. When the user clicks the back button, the last page pushed onto the stack is popped off of the stack and loaded in the browser window. When all of the pages are popped off of the stack, the back button grays out, indicating that the stack is empty.
Note that the forward button also uses a stack, but it works on a slightly different basis. Clicking the back button pushes the current page on the stack and clicking the forward button pops the top page off of the stack. Visiting a new page without clicking either button automatically empties the forward button stack.
Check whether a string of parentheses is balanced or not.
For example, return True for these input strings:
(()())
([]{{}}[])
but False for these strings:
(()
([)(])
You can solve this using recursion, but a very efficient and clear solution would be to iterate over the string, whenever you encounter an opening symbol, you push it into the stack. Whenever you encounter a closing symbol you pop from the stack and check that that the types match.
I like the pez dispenser.
Also the stack of papers (where the actual human interaction is never to take the top item but rather to take the second from the top.
At some point you have to talk about pancakes and the fact that people don't actually eat them as a stack -- they frequently destroy stack integrity by cutting top to bottom. I personally use a stack of pancakes as a queue, extracting one at a time from the btotom as it soaks up syrup but I've been told I'm an odd one :-)
The "real-life" examples are pretty clearly delineated here already, but since you asked for examples in programming as well, I'll add one to the list.
Stacks can be used to build calculators. There's a great assignment in CS50 AP called Calc 2.0. Students build a command-line calculator in C using a stack to store the numbers passed in by the user. Additionally, it's an opportunity to teach students about prefix notion as opposed to their normal use of infix notation.
The problem specification explains why this approach is worth pursuing:
Visually, this approach of "finding the rightmost operator and applying it to the two numbers to its right" is an intuitive way for humans to parse prefix notation, but computers can be a bit smarter about this, without ever having to look at each operand or operator more than once, if instead we store all the information in a stack as we see it.
If the computer parsed this input by starting at the right side (aka the last element of
argv) and pushing numbers onto a stack as it came across them, then when it came upon an operation all that would need to happen is to pop the top two numbers off the stack, apply the operation, and push the result back on!
Here is the boilerplate they are given for building a stack:
typedef struct
{
int size;
float nums[MAXNUMS];
}
stack;
It's a simple struct, but since students can easily error-check their own work with simple math, this assignment provides a great way to actually start using a stack for something meaningful that also builds on students' prior knowledge.
In practice, many calculators employ the Shunting Yard algorithm to evaluate mathematical expressions as per the rules of BODMAS. The algorithm makes use of stacks to push and pop operators based on precedence and position.
This won't work for all students, but some will likely be familiar with the very popular collectable card game Magic: The Gathering.
In this game, spells are cast to "the stack", with the last spell cast resolving first. During resolution of the stack, more spells may be cast to the top of the stack.
Much of what has been said already is wonderful. I would like to point out that Mike's Pez dispenser visualization is brilliant, and lends itself to a direct lesson with manipulables. You can take a few of them into an actual classroom, mix up various Pez colors, and show all of the standard operations of a stack in a way that they can physically play with. Pop, push, peek, and isEmpty are all clearly defined operations in a real life Pez dispenser.
Let the kids wash their hands, and then use tiny bits of paper that the kids write on and place on top of a pez brick prior to loading it into the dispenser, and you will have a natural toy with all of the standard operations. And it goes without saying that the kids will love to eat the results of each pop operation as they sort out their algorithms. :)
I also wanted to add that if your kids are familiar with linked lists, that is a great way to show a stack implementation.
Where stacks matter a tremendous amount in my instruction is in AP Computer Science A when talking about variable storage and scope, and in our Data Structures course when we talk about how function calls operate.
Here are couple of examples which don't employ objects resembling real-life stack:
contained_in(BiggerDoll, SmallerDoll) as a model for stack. push in this context would be equivalent to encasing a stack of Russian dolls in a yet bigger Russian doll, pop would be equivalent to opening the outermost doll and extracting the remaining dolls.push is when the characters enter a dream, and pop is when they wake up from the dream. Characters must wake up from their dreams in the exact reverse order from the one in which they entered them.pushing half of it on a stack and then poping the other half.In my view, a good computer science example for stack-oriented processing is the PostScript language.
The Hello world example from the Wikipedia page shows the Reverse Polish (postfix) notation used in PostScript (similar to the CS50 AP Calc 2.0 Peter showed in his answer that uses prefix notation):
%!PS
/Courier % name the desired font
20 selectfont % choose the size in points and establish
% the font as the current one
72 500 moveto % position the current point at
% coordinates 72, 500 (the origin is at the
% lower-left corner of the page)
(Hello world!) show % stroke the text in parentheses
showpage % print all on the page
Input tokens would be pushed on a stack as they are parsed, and when an operator or command is encountered that needs n arguments, the upper n tokens would be popped from the stack, used for calculation or function execution and any result pushed on the stack again.
This can even better be seen in the example that draws a line, using a conversion from PostScript points to millimeters:
/mm {360 mul 127 div} def
0 0 moveto
0 40 mm lineto stroke
The first line defines¹ a conversion function mm which is used in the third line to draw a vertical line 40 mm long. The function pops the top element from the stack, multiplies it with 360, divides it by 127 and pushes the result on the stack again.
¹ In fact, the def command, which defines a function, will not put its result back on the stack but into a dictionary which is used to look up commands.
I am not a computer science educator at all, but this question immediately reminded me of Leo Brodie's book Starting Forth from 1981 (!) with some cute visualizations of stack manipulations. This links up with @Dubu's answer about the PostScript language.
They've presumably already learned about functions, so if you use that as the example, you both teach them about stacks and give them a deeper understanding of how functions work.
I would take it in two main phases, using code similar to this as an example.
h(c) {
print(c)
return
}
g(b) {
h(b + 3)
print("foo")
return
}
f(a) {
x = 42
g(x)
h(x)
print("bar")
return
}
First, focus on how the return always knows to transfer control to the statement after the line the function was called on. So for instance, the return from h might go to either g or f, depending on where it was called from, and in the former case, g in turn knows where it was called from. If the language they're using is one that prints the call stack when it crashes, they're probably already somewhat familiar with this.
Make sure they fully understand how the control flow works first, then bring in the concept of a stack and explain how you can implement function calls by storing the return addresses on the stack whenever you call a function, and popping them whenever you return.
Once they understand that, you might want to proceed to explain how parameters are stored on the stack. That might confuse them a bit, though, since you can't access elements other than the one on top in a "theoretically pure" stack, but you do when accessing values in the stack frame. I would probably just mention to them that the reality is a bit more complicated than what you just described, but save the details for a later lesson.
A stack can be used to verify that an HTML document is well-formed. You begin with an empty stack.
When a tag opens (say <p>), the tag's type, in this case, "p", onto the stack.
When a tag is self-closing, do nothing.
When a tag closes, (say </p>), check to see that it matches the tag on the top of the stack by peeking at it. If there is a match, pop the stack. If there is a mismatch, emit an error message telling where the error lurks in the HTML file you are scanning.
If, at any time in the process you find an empty stack, report an error.
At the end:
If there are still tags on the stack, you have unclosed tags; report an error.
If the stack is empty, your HTML file has balanced tags.
Packing a suitcase: the items last to be packed are the first to come out (assuming you place items directly on top of each other)
A couple of others: -- A stack of papers -- A stack of chairs
A refrigerator: You put food in the freezer. To take out oldest food, first, you need to take out all newer food.
History in your browser, recurrence in functions, "undo" like control-z in many programs are examples of stack usage
