Stacks
A stack is a linear data structure that we use when we care most about the top item (the one that is most recently added). Adding or removing is always done at the top and happens in O(1) time. Stacks operate in last-in-first-out (LIFO) order. The last item (most recent) is the first one that will be removed.
Think of your browser's "back" button — you only care about the page you most recently visited. You add items to the stack as you visit more pages. When you click "back", the browser grabs the page from the top of the stack and displays it to you. As you continue to click back, you get the pages starting from the one most recently visited and move backward until you reach the page you first visited.
Cheat Sheet
| Big O Complexity | |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
| space | O(n) |
- Fast Access at the Last ItemWe can add/remove/access the last item in O(1) time.
- OrderedThe data is ordered where the most recently added items are at the top of the stack, and the oldest items are at the bottom.
- Slow LookupsTo access any item other than the top, it will take O(n) time to iterate through the stack and find it.
Stacks in Interviews
- Balancing brackets / parentheses
([[()]]) - Managing minimum or maximum values
- Build a queue using stacks
Stacks Explained
A simple real-world analogy of a stack is a pile of dirty dishes in your sink. You can continue to add a dish to the top after every meal, and when you go to clean them, you start with the top dish (the last added) and work your way to the bottom (the first added). Adding or removing is always done at the top, and the plates are stored linearly. If you wanted to grab a dish in the middle, you would have to remove all the ones on top of it first.
Stacks are essential in computer science and foundational to how our code runs. You may have heard the terms "call stack", "stack trace", or "stack overflow". When we call functions or execute operations, they often call additional functions. These accumulate in a stack until you reach the last item called. Once the final function is called, it calculates its result, and then it passes that value to the item before it in the stack that needed it. Our code must execute in this order since each step requires a result from another function. It will work from the top of the stack down to the initial function that was executed.
The below example is a high-level demo of what happens with a call stack.
It builds the stack up to the final operation needed to calculate the total and unwinds once it gets back to the initial run function, at which point it is complete.
The call stack is this list of functions/operations that must occur in order for our code to run. A stack overflow happens when the call stack grows larger than the memory of our computer. A stack trace shows the order of the call stack when an error occurs so we can figure out where the bug happened.
Higher-level implementations of stacks we see:
- Undo button: it stores revisions linearly, and we can get to the most recent version of a document when we hit undo
- Back button in a browser: the pages we visit are stored as a stack
- Messages or emails are typically presented with the most recently added first
- Depth-first search