Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
0 / 10 · LIFO
READY
Stack is empty
Push a value to begin. A stack only ever grows and shrinks at the top.
Value
Intuition
Think of a stack of plates in a cafeteria. You can only add a new plate to the top (Push) and remove the top plate (Pop). The last plate added is the first one to be removed. This is known as LIFO (Last In, First Out).
Concept
A stack only ever lets you touch one end: the top. The item you added most recently is the one you get back first, which is what last in, first out (LIFO) means. Because push, pop and peek all work on the top and never search, each one is O(1). A browser's back button is a stack of pages: the page you left most recently is the one it returns you to.
How it Works
We maintain a pointer (often called 'top') that tracks the last element added.
- Push: Increment top index, add element at top.
- Pop: Return element at top, decrement top index.
- Peek: Return element at top without changing top index.
Step-by-Step Breakdown
- Start Empty: Stack is empty, top is -1.
- Push(10): Top becomes 0, Stack[0] = 10.
- Push(20): Top becomes 1, Stack[1] = 20.
- Pop(): Return Stack[1] (20), Top becomes 0.
Example trace
Push(5)
5 is added to the empty stack.
[5]
Push(8)
8 is placed on top of 5.
[5, 8]
Pop()
Remove the top element (8). 5 becomes the new top.
[5]
When to Use
- LIFO Processing: When you need to access the most recently added element first (e.g., Undo).
- Backtracking: Storing previous states to return to them (e.g., Maze solving).
- Parsing: Syntax checking (parentheses) and expression evaluation.
When NOT to Use
- Random Access: Accessing the
k-thelement is O(n), unlike Arrays O(1). - Searching: Finding an item requires popping elements off, destroying the stack order.
How to Identify
Look for problems involving nested structures (like parentheses), reversing sequences, or finding the "nearest" element with a certain property. Keywords: "Last In First Out", "Undo/Redo", "Back/Forward", "Parentheses".
Preparing for interviews? This topic is also taught as a pattern:
Stack Overview
Applying for software engineering roles? Free, no sign-up: