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."
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 |
Java comes with a built in stack implementation , but it's better to use Deques instead.
The stack implementation has a few big drawbacks: it doesn't have an interface and it extends the Vector class, which has thread synchronization overhead.
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
