Linear
Stack Fundamentals
LIFO order, O(1) push and pop. The structure behind function calls, undo systems, and every backtracking algorithm.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Stack?
LIFO — last in, first out — is the defining constraint of a stack: every insertion and every removal happens at one end only, the top. That constraint is what makes stacks the natural match for function call management, undo history, bracket matching, and any algorithm that must retrace its steps in reverse order. There is no random access, no searching, no way to inspect anything below the top — the restriction is the feature, not a limitation. Under the hood, Java's ArrayDeque implements a stack with a resizable array and a top-of-stack pointer; push and pop move that pointer in O(1) without shifting any elements. The JVM's own call stack is literally a stack of frames — each method call pushes a frame, each return pops one, and StackOverflowError means the stack ran out of space.
Analogy: A stack of dinner plates in a cafeteria spring-loaded dispenser. You can only take the top plate — you cannot reach in and grab the third one without removing the two above it first. Every plate you add goes on top, and every plate you remove comes from the top. The last plate added is always the first one taken. That constraint — LIFO — is not a limitation; it is the entire point.
02
Section Two · Mental Model
How It Thinks
Only the top element is accessible
▶
Push and pop are always O(1) — no traversal, no shifting
LIFO order is structurally enforced
▶
Naturally models function calls, undo history, and bracket matching
No index access, no search
▶
The constraint is the feature — misuse is impossible by design
Backed by a resizable array (ArrayDeque)
▶
No linked-list pointer overhead — cache-friendly, memory-efficient
Empty stack has no top element
▶
Always check isEmpty() before peek() or pop() — both throw on empty
03
Section Three · Operations
Core Operations
Push
Places a new element on top of the stack, increasing the size by one in O(1) time.
Pseudocode
function push(stack, value):
stack.addFirst(value) // O(1) — moves top pointer up // amortized O(1) if backing array resizes
Push — add 40 to top of stack
ArrayDeque.push() vs addFirst():
- Deque<Integer> stack = new ArrayDeque<>() — then call push() which is an alias for addFirst().
- Both are O(1). Avoid add() which appends to the tail — the wrong end for stack semantics.
Pop
Removes and returns the top element of the stack, decreasing the size by one in O(1) time.
Pseudocode
function pop(stack):
if stack is empty:
throw EmptyStackException // guard — always check first return stack.removeFirst() // O(1) — moves top pointer down
Pop — remove top element from stack
Pop throws — always guard with isEmpty():
- Calling pop() or removeFirst() on an empty ArrayDeque throws NoSuchElementException at runtime — no compile-time warning.
- The pattern is always: if (!stack.isEmpty()) stack.pop(). For null instead of an exception, use pollFirst().
Peek
Returns the top element without removing it, allowing inspection of the stack's current state in O(1) time.
Pseudocode
function peek(stack):
if stack is empty:
throw EmptyStackException // guard return stack.peekFirst() // O(1) — reads without removing
peek() vs peekFirst() vs element():
- On ArrayDeque used as a stack: peekFirst() returns null if empty, element() throws if empty.
- Use peekFirst() when an empty stack is a valid state your code should handle; use element() when empty means a bug and you want to fail loudly.
isEmpty
Returns true if the stack contains no elements, preventing pop() and peek() from throwing on an empty stack.
Pseudocode
function isEmpty(stack):
return stack.size() == 0 // O(1) — size is a stored field
Guard every pop and peek:
- isEmpty() is not optional ceremony — it is the mandatory guard before every pop() and peek().
- In interview code, missing this check is an instant red flag. Write the guard first, then the operation.
Reverse a Collection
Uses a stack's LIFO property to reverse the order of any sequence by pushing all elements then popping them back.
Pseudocode
function reverse(array):
stack = new Stack
for each element in array:
push(stack, element) // push all — O(n)
result = new Array[array.length]
for i from 0 to array.length - 1:
result[i] = pop(stack) // pop all — O(n) return result // O(n) total, O(n) space
Reverse — push all, pop all
LIFO reversal is the canonical stack use case:
- Any time you need to process items in reverse order without knowing the total count upfront, push them all and pop them back.
- This pattern also underlies iterative DFS, the call stack simulation in tree traversal, and undo/redo systems.
Common Mistake: Using the legacy Stack class from java.util. Stack extends Vector, which synchronizes every method — push, pop, peek, and isEmpty all acquire a lock on every call, even in single-threaded code. The correct replacement is Deque<T> stack = new ArrayDeque<>() — same interface, no lock overhead, and it does not expose get(index) or other methods that violate stack semantics.
04
Section Four · Implementation
Build It Once
Build this from scratch once — it makes the mechanics concrete. In any real project or interview, reach for ArrayDeque (Section 05).
Java — Stack core mechanics
// Build once to understand the mechanics — use ArrayDeque in practice. public class Stack {
private int[] data;
private int top; // index of the top element, -1 when empty public Stack(int capacity) {
data = new int[capacity];
top = -1;
}
// O(1) — place value at top, move pointer up public void push(int value) {
if (top == data.length - 1) resize();
data[++top] = value; // increment first, then write
}
// O(1) — read value at top, move pointer down public int pop() {
if (top == -1) throw new RuntimeException("empty");
return data[top--]; // read first, then decrement
}
// O(1) — read without modifying the pointer public int peek() {
if (top == -1) throw new RuntimeException("empty");
return data[top];
}
}
Stack — Full Implementation
Java — Complete Stack implementation
import java.util.Arrays;
public class Stack<T> {
private Object[] data;
private int top;
private static final int DEFAULT_CAPACITY = 8;
public Stack() { data = new Object[DEFAULT_CAPACITY]; top = -1; }
public Stack(int capacity) { data = new Object[capacity]; top = -1; }
// O(1) amortized — push to top public void push(T value) {
if (top == data.length - 1) resize();
data[++top] = value;
}
// O(1) — remove and return top
@SuppressWarnings("unchecked")
public T pop() {
if (top == -1) throw new RuntimeException("Stack is empty");
T value = (T) data[top];
data[top--] = null; // GC hygiene return value;
}
// O(1) — read top without removing
@SuppressWarnings("unchecked")
public T peek() {
if (top == -1) throw new RuntimeException("Stack is empty");
return (T) data[top];
}
// O(1) public boolean isEmpty() { return top == -1; }
public int size() { return top + 1; }
// O(n) — 1-based position from top (1 = top element) public int search(T value) {
for (int i = top; i >= 0; i--)
if (data[i] != null && data[i].equals(value))
return top - i + 1;
return -1;
}
// O(n) — double the backing array private void resize() {
data = Arrays.copyOf(data, data.length * 2);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("Stack[top→ ");
for (int i = top; i >= 0; i--) {
sb.append(data[i]);
if (i > 0) sb.append(", ");
}
return sb.append("]").toString();
}
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
// 1. Push 4 elements
s.push(10); s.push(20); s.push(30); s.push(40);
System.out.println(s); // Stack[top→ 40, 30, 20, 10] // 2. Peek without removing
System.out.println(s.peek()); // 40 // 3. Pop twice
s.pop(); s.pop();
System.out.println(s); // Stack[top→ 20, 10] // 4. isEmpty check
System.out.println(s.isEmpty()); // false
s.pop(); s.pop();
System.out.println(s.isEmpty()); // true // 5. Search — 1-based position from top
s.push(5); s.push(15); s.push(25);
System.out.println(s.search(15)); // 2 (second from top)
}
}
Python — Built-in list as stack + manual ArrayStack
# Python's list IS a stack when used from the right end:
stack = []
stack.append(10) # O(1) amortized — push
stack.append(20)
stack[-1] # O(1) — peek (last element = top)
stack.pop() # O(1) amortized — pop from end
len(stack) == 0 # O(1) — isEmpty # ─── Manual implementation for understanding ─── class ArrayStack:
def __init__(self, capacity=8):
self._data = [None] * capacity
self._top = -1 def push(self, value): # O(1) amortized if self._top == len(self._data) - 1:
self._resize()
self._top += 1
self._data[self._top] = value
def pop(self): # O(1) if self._top == -1:
raise IndexError("stack is empty")
value = self._data[self._top]
self._data[self._top] = None
self._top -= 1 return value
def peek(self): # O(1) if self._top == -1:
raise IndexError("stack is empty")
return self._data[self._top]
def is_empty(self): # O(1) return self._top == -1 def __len__(self): # O(1) return self._top + 1 def _resize(self): # O(n)
self._data = self._data + [None] * len(self._data)
def __str__(self):
items = [str(self._data[i]) for i in range(self._top, -1, -1)]
return "Stack[top→ " + ", ".join(items) + "]"
05
Section Five · Java Built-in
Use It In Java
IN JAVA
Use
Deque<T> stack = new ArrayDeque<>() Import
import java.util.ArrayDeque; import java.util.Deque; | Method | Complexity | Note |
|---|---|---|
push(value) | O(1) amort | Alias for addFirst() — adds to top |
pop() | O(1) | Removes + returns top; throws if empty |
peek() | O(1) | Returns top without removing; null if empty |
pollFirst() | O(1) | Like pop() but returns null instead of throwing |
peekFirst() | O(1) | Like peek() — prefer for null safety |
isEmpty() | O(1) | Always call before pop() or peek() |
size() | O(1) | Number of elements currently in stack |
⚠ Gotcha: Deque has two ends — push() and pop() operate on the HEAD (front), which is the top of the stack. If you accidentally call addLast() or removeLast() you are operating on the wrong end and your stack is silently broken. Always use push/pop/peek or addFirst/removeFirst/peekFirst — never the Last variants on a stack.
Choose Use ArrayDeque when you need a stack. It is backed by a resizable array with no synchronization overhead. Use LinkedList only if you are already using it for other operations and want to avoid a second object — ArrayDeque is faster in all pure stack use cases.
06
Section Six · Decision Guide
Pick The Right Structure
Decision Flowchart
Comparison Table
| Structure | Push/Pop | Peek | Thread-safe | Verdict |
|---|---|---|---|---|
| ArrayDeque as Stack ← this | O(1) | O(1) | No (use intentionally) | Correct choice |
| Legacy Stack class | O(1) | O(1) | Yes (synchronized) | Avoid — lock overhead |
| LinkedList as Stack | O(1) | O(1) | No | Works, cache-unfriendly |
| ArrayList as Stack | O(1) amort | O(1) | No | Works (get last), non-idiomatic |
07
Section Seven · Practice
Problems To Solve
Two patterns unlock most stack interview problems: monotonic stack (maintaining a stack where elements are always in sorted order — increasing or decreasing — to find next greater/smaller elements efficiently) and nested structure unwinding (using the stack to match opening and closing delimiters, or to reverse/decode nested sequences). Look for problem descriptions containing "next greater", "previous smaller", "valid brackets", "decode", or "evaluate expression" — they signal stack-based solutions.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | monotonic | Valid Parentheses | Push every opening bracket onto the stack — when you encounter a closing bracket, the top must be its exact matching opener or the string is invalid. |
| Medium | monotonic | Min Stack | Maintain a second parallel stack that tracks the running minimum — push to it only when the new value is less than or equal to the current minimum top. |
| Medium | monotonic | Daily Temperatures | A monotonic decreasing stack of indices — when you find a warmer day, pop indices and record the gap between the current index and the popped index. |
| Medium | monotonic | Basic Calculator II | Push numbers onto the stack; when you see * or /, pop and evaluate immediately — defer + and - until the end by pushing signed values. |
| Medium | reversal | Decode String | Two stacks — one for repeat counts, one for the string built so far — let you cleanly unwind nested brackets without recursion. |
| Hard | monotonic | Largest Rectangle in Histogram | A monotonic increasing stack of indices tells you, for each bar, exactly how far left it can extend as the shortest bar in a potential rectangle. |
Interview Pattern:
- The monotonic stack solves roughly 60% of stack interview problems — any time a problem asks for the "next greater element", "nearest smaller value", or "maximum rectangle", think monotonic stack first.
- The second pattern — using a stack to match or unwind nested structure — covers bracket validation, expression evaluation, and string decoding.
- Recognise the pattern and the solution structure follows immediately.