Stacks
Have you ever used a text editing document (e.g. Microsoft Word, Google Docs) to write an essay? In this situation, it is useful to be able to keep track of the last several commands you performed. That way you can simply back out of a mistake (or mistakes) and “undo” them when applicable.
How do we keep track of the last several commands performed though?
We can use a stack!
Introduction (Beginner):
A stack is a data structure used to store a bunch of data, and then access the data in the opposite order that the data was stored. This process is commonly described as “last in, first out”, or LIFO.
You can think of a stack as a pile of books placed in vertical order. When we’re piling the books up, we first place (push) book 1, then book 2 on top of book 1, and finally book 3 on top of book 2. Now in order to retrieve book 1, we need to first remove (pop) book 3, then remove book 2. This book analogy illustrates the “last in, first out” nature of the stack data structure – the last book that is placed (pushed) on the pile is the first book to be removed (popped).
Examples (Intermediate):
Now let’s see how a stack can help us undo mistakes in a document-editing scenario.
Imagine you are an elementary English teacher planning a vocabulary lesson for your first grade students. You start off by writing “cars”, “dogs”, “cats”, then “ICT” on a word document. You suddenly realize that “ICT”, short for Information and Communication Technology, probably shouldn’t be on the vocabulary list for a first-grader. Luckily, you hit the undo button on Google Docs, and “ICT” disappears. This process can be modeled by a stack. As you record the terms, “cars”, “dogs”, “cats”, and “ICT” are pushed onto the stack one by one. When you hit the undo button, you are essentially popping off the most recent word you added to the document (“ICT”) from the stack.
There are so many more real-life examples of stacks, such as car decks, cafeteria trays, and breakfast pancakes.
The “back button” on a web browser is also an excellent example of stack implementation. When a user visits a new web page, the current page is pushed onto the stack. When the user clicks the “back button”, the last page pushed onto the stack is popped off and loaded into the browser window. When all the pages are popped off of the stack, the back button will gray out, signaling that the stack is empty. The “forward button” works in a similar but slightly different way. While clicking the “back button” pushes the current page onto the stack, clicking the “forward button” pops the top page off the stack. When you visit a new page without clicking either button, the forward button stack is automatically emptied. In class, I usually run through a web demonstration of clicking a series of back buttons and forward buttons to better illustrate how stacks work.
Memory (Advanced):
If you have some experience in programming, you’ve probably used “Stack Overflow”, a Q&A website for software development. But what exactly does the term “stack overflow” mean in Computer Science? The “stack” here refers to the memory stack, which stores data in a computer’s memory. In computer programs, the memory stack stores local variables contained by a function. Since it is fixed in size, the memory stack is designed to be temporary – when computational tasks are complete, the memory of the variables are automatically erased.
A stack overflow is a run-time software bug when a program attempts to use more space than is available on the memory stack, which results in a program crash. The most typical case of a stack overflow error happens when your code executes an infinite or very deep recursion (a function invoking itself). Whenever a function is invoked, some part of the stack memory is consumed. Since the memory stack is fixed in size, once all the memory is exhausted with consecutive recursive function calls, a stack overflow error will be thrown. Note that a stack overflow error should be differentiated from a run-time error, which is typically caused by an infinite loop.
Conclusion:
From organizing books and undoing document changes to navigating with web browsers and utilizing computer memory, stacks are more relevant to our daily lives than you think!
Hi Eric! I loved reading this post – even as someone with a computer science background who has learned about stacks in the past, this post is a great refresher on the usefulness of stacks! I really liked how you split the information about stacks into beginner, intermediate, and advanced levels – I found that it made the information more organized and easier to digest. I also appreciate the use of visuals to illustrate the concepts you’re talking about – I definitely think my own blog posts that are more technical in nature could benefit from diagrams and visuals!
Hey Eric! I really enjoyed reading your blog post! This was a fantastic introduction guide to a pretty technical topic that non-computer science people are usually quite foreign too. You explained it very simply and elegantly with some great examples too. The illustrations were extremely helpful, and I liked how specific they were too. Furthermore, your additional more “advanced” section was definitely interesting. It provided a more in-depth example or situation where stacks can become problematic. However, I think a greater warning might be necessary for readers. You go from the regular section directly to the “advanced”, yet a person who finished the regular section might not have the required background still for some concepts in the advanced section. I think a disclaimed would be sufficient.