Interview Cake
Quick reference
| Worst Case | |
|---|---|
| space | |
| push | |
| pop | |
| peek |
A stack stores items in a last-in, first-out (LIFO) order.
Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."
Loading...
Strengths:
- Fast operations. All stack operations take time.
Uses:
- The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.
- Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.
- String parsing—stacks turn out to be useful for several types of string parsing.
Implementation
You can implement a stack with either a linked list or a dynamic array—they both work pretty well:
| Stack Push | Stack Pop | |
|---|---|---|
| Linked Lists | insert at head | remove at head |
| Dynamic Arrays | append | remove last element |
