May 9, 2021
Popping off on Stacks!
The beginning of my CS journey was a mix of frustration and wonder. I can pinpoint when my interest really took hold: data structures. The simplest of operations performed with various data structures had me in awe the first time I saw them. This was specifically prevalent with stacks, so that’s what we’ll be chatting a bit about today.
What’s a stack?
For starters, a stack is a linear data structure. This just means we can look at it as a special super cool type of array or list. What makes a stack a stack is that it follows one rule: “The first item that goes in the stack, is the last item out of the stack” This can also be inverted as “The last item in is the first one out”. I see too many references to a stack of plates, and although fitting, I like the idea of a vending machine a bit more. When a vending machine is loaded up with cans of soda, the first can of Coke inserted at ‘A1’ or whatever selection spot, is going to be the last one to come out of that section right? The last can placed there is what’s going to be spit out when someone pops those coins in and makes that selection. (That’s about it! Not too bad right?)
How does this ‘stack’ up in code?
(I’m super funny)
I found the easiest way to visualize a stack in code was to use Python using a list since the code seems to be pretty straightforward to read. There are many different ways to implement a stack like using a linked list or various libraries like deque or queue! I’d encourage taking a peek at the many different possibilities in your language of choice.
Regardless of the implementation, most stacks all share a few operations in common:
- push(item) — Adds ‘item’ element to the top of the stack
- pop() — Deletes the top element of the stack
- top() or peek() — Returns the element at the top of the stack
- empty() — Lets us know whether or not our stack is empty
Method credit => https://www.geeksforgeeks.org/stack-in-python/
There can be a few other useful methods, but these cover the basics.
What if I’m a visual learner?
No sweat! I’ve got a few visuals here to hopefully help us ‘stack’ up against the competition. These visuals correlate directly to the code example above.
Where would I use this in my ‘stack’ of everyday problems?!
If you’re here reading about stacks, chances are you’ve worked in some sort of IDE or code editor that gives you the squiggly red lines when you miss parentheses right? If not, here’s a quick look:
How the heck does it know I’m missing parentheses, and how does it figure it out?
One of the most common forms of stack knowledge flexing comes in the form of a ‘parentheses validation’ problem. Let’s say I give you a text file and ask you whether or not the parentheses all have a match, and there are no outliers. How can we get our computer to figure it out? This gave me a ‘stack’ of headaches prior to learning about our data structure of the day.
If you’d like to try to figure it out without any spoilers, here’s this exact problem on leet code!
If you want to see the stack in action, check out this video explanation of the solution! (No affiliation, I just thought the drawing was super helpful)
Let’s pop this stack
That’s about all I have on stacks for now. I’m sure I’ll find a few more fun and exciting ways to use them in my upcoming years, as I’m sure you will too! Keep an eye out for the stacks around you. It’s super neat to see how a structure so simple can be the foundation for so many bigger things!
Citations:
Basic stack info: https://www.geeksforgeeks.org/stack-in-python/
Leetcode Solution:https://youtu.be/8xqZgLYaIpY?t=618
Utilized Google Jamboard and replit for visuals and code examples
