# What are some good examples of using a stack data structure?

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?

• Could you please add a context? What is the level of the students? – ItamarG3 Jun 18 '17 at 11:42
• High school students I'm teaching next year for their בגרות exam. They have only some basic knowledge in procedural programming and the tip of the iceberg in Object-Oriented stuff. – Yotam Salmon Jun 18 '17 at 12:44
• Again, you need to write these things in the question itself. BTW, בגרות are called matriculation exams (or finals) in english ;) – ItamarG3 Jun 18 '17 at 12:44
• I knew about the word "matriculation", just wasn't sure if those exams are actually known by this name (I have never heard anyone using this word in English so I wasn't confident about using it). Added the info to the question, thank you for the tip. – Yotam Salmon Jun 18 '17 at 12:48
• Does "Pole of rings" mean Towers of Hanoi? I was going to suggest that, although it is better as an example of recursion. But they are related, so that seems good! – user737 Jun 18 '17 at 16:00

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.

• Wow, that's a great example! I love it! – Yotam Salmon Jun 18 '17 at 16:27

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.

• The spring-loaded stack of trays in a (university) cafeteria was in fact the origin of the name of the data structure, at least according to common legend. – Jörg W Mittag Jun 18 '17 at 14:41
• I had an A-Level computing teacher who got so carried away with explaining the mechanism of the stack of plates he forgot that he was supposed to actually be explaining a stack in computing terms. – Muzer Jun 19 '17 at 8:54

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:

1. Push - adding a new element (bullet) to the top.
2. Pop - remove the top element (bullet) from the stack (in the analogy, this is like shooting).
3. Peek - looking at the first element of the stack (checking to make sure that the topmost bullet is correctly placed)
4. Check if Empty - check if the stack is empty (in the analogy, this operation is checking if there are bullets left)
5. (Initializing the stack - creating a new stack)

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.

• Of course, but that's the definition of the stack. I'll definitely explain that as an origin to the name of the stack, but I need some use-cases for programming and life. (I hope I'm clear enough) – Yotam Salmon Jun 18 '17 at 12:41
• @YotamSalmon then you should write that in your question. I'll edit my answer soon. – ItamarG3 Jun 18 '17 at 12:44
• @YotamSalmon edited the answer :) – ItamarG3 Jun 18 '17 at 12:59
• Tracing links and the Undo operation should be familiar examples. – user737 Jun 18 '17 at 16:05
• I would definitely mention the browser's back button. It provides a non-metaphorical example, that's easy to understand, and demonstratively proves that stacks are useful in programming. – Phoenix Jun 18 '17 at 17:32

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.

• This is an excellent, intuitive example. Welcome to CSE! I hope we hear more from you in the future. – Ben I. Jun 19 '17 at 18:51
• Excellent!! This is only example which is comprehensible to a common man!! – Failed Scientist Sep 8 '17 at 7:10

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 run this lab every year. I can vouch that it's a good lab :) Welcome to CSE! I hope we hear more from you in the future! – Ben I. Jun 19 '17 at 19:53
• It's worth noting that recursive solution is really the same, just using underlying call stack - so it's not explicitly visible. – Frax Apr 27 '18 at 11:15

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 :-)

• I treat pancakes as stack, popping the top one off and dunking it in the syrup that's sitting on the side. But that might just be me. :) – Scimonster Jun 18 '17 at 11:47
• Pancakes as a stack or as a queue -- is there anything they can't do???? :-) – Mike Zamansky Jun 18 '17 at 11:54
• Stack, or queue, doesn't matter much, they get consumed either way. That's something that's usually left out of stack lessons: that the stack is consumed. As to pancakes and what can't they do: Survive long on my plate. :) – Gypsy Spellweaver Jun 18 '17 at 11:59
• I was thinking of a messy desk piled with papers, but maybe we don't want to encourage that? – user737 Jun 18 '17 at 16:04

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.

• You can, of course, use postfix as well and show the workings of a RPN (Reverse Polish Notation) calculator such as the HP15C, my all time favorite calculator. 3 4 5 * + yields 23. – Buffy Jul 12 '17 at 12:13

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.

• It's a nice example to be sure, but if you try this with your class, be aware that Shunting Yard can be tricky for kids who are just at the point where they are learning about stacks. You have to break this one down very carefully for them. – Ben I. Jun 18 '17 at 17:56
• You can always start with the analogous railroad junction and talk about how you have to re-order the cars in a way that's easier to evaluate programmatically. – Patrick Roberts Jun 19 '17 at 16:24

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:

• Russian doll (matryoshka). It is a stack if you use the relationship 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.
• Literary figure "story within a story" (or "dream within a dream"), although the analogy is a little imprecise since any "inner" story can be observed from an "outer" story. The examples of such stories are plentiful, but since this should appeal to high-school students, I think, the movie Inception (the one starring DiCaprio) could be used. In this movie, the 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.
• Palindrome. I.e. the way to recognize one by pushing half of it on a stack and then poping the other half.
• Welcome to Computer Science Educators! Could you add some details on how the first two are an example of a stack? – ItamarG3 Jun 19 '17 at 11:24
• @ItamarGreen OK. – wvxvw Jun 19 '17 at 11:31
• The first example really is a very good one. – ItamarG3 Jun 19 '17 at 11:37

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.

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.

• Welcome to cseducators! This is a very nice use-case. I hope we hear more from you in the future. – Ben I. Jun 19 '17 at 13:07
• I note that postscript is built on a Forth language base. Forth itself is stack oriented. – Buffy Jul 12 '17 at 12:07
• In Australia at least, many supermarkets store shopping trolleys in a dead-end corral. So when you get a trolley for your shopping it will be the last one someone previously pushed into the corral.
• The paper into a photocopier tray
• For a Biblical reference: Matthew 20:16
• The way many of us process interruptions. We pause one task to focus on the interruption. We might pause that task to work on a subsequent interruption. Repeat for as many levels as you want. And then as each task is completed we return to the previous interrupt level.
• Welcome to CSE! Good example about processing interruptions. But isn't Matthew 20:16 really more of an example of list reversal? ;-) I hope we'll hear more from you in the future. – Ben I. Jun 19 '17 at 3:06

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.

# The call stack

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

• This answer could really benefit from more explanation. Could you add some explanation to how those examples are a stack? – ItamarG3 Jun 20 '17 at 5:39

A refrigerator: You put food in the freezer. To take out oldest food, first, you need to take out all newer food.