🟢 Junior Level

Stack — data structure following LIFO principle (Last In, First Out).

Simple analogy: Stack of plates. You put on top, you take from top.

Why LIFO is needed: last added element is the most relevant. Examples: undo actions (Ctrl+Z), method calls (call stack), bracket parsing, DFS (depth-first graph traversal).

Operations:

• push(e) — put on top
• pop() — take from top
• peek() — view top element

// ❌ Don't use java.util.Stack
Stack<String> stack = new Stack<>();  // Legacy!

// ✅ Use ArrayDeque
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.pop();  // → "B" (last in, first out)

---

🟡 Middle Level

Why java.util.Stack is bad

// Stack extends Vector!
public class Stack<E> extends Vector<E> { ... }

// Problems:
// 1. All methods synchronized → slow
// 2. Can call get(0), add(0, e) → breaks LIFO
// 3. Inheritance from Vector = legacy

Correct alternative: ArrayDeque

// ✅ ArrayDeque — fast, no synchronization
Deque<String> stack = new ArrayDeque<>();

stack.push("A");      // Push
stack.push("B");
String top = stack.peek();  // "B" — peeked
String popped = stack.pop(); // "B" — popped

// Exceptions:
// pop() on empty → NoSuchElementException
// peek() on empty → null

Comparison

	Stack	ArrayDeque	LinkedList
push/pop	O(1)	O(1)	O(1)
Synchronization	Yes	No	No
Memory	Medium	Low	High
Can get(index)	❌ Yes (bad! get(index) allows accessing elements not through top, breaking LIFO semantics. Client may accidentally use stack as list)	❌ No	❌ No

Use Cases

// 1. Undo/Redo
Deque<Action> undo = new ArrayDeque<>();
undo.push(action);
Action last = undo.pop();

// 2. Bracket validation
Deque<Character> stack = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
    if (c == '(') stack.push(c);
    if (c == ')') stack.pop();
}

// 3. DFS (depth-first traversal)
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);

---

🔴 Senior Level

When NOT to use stack

1. If random access needed — use List
2. If FIFO processing needed — use Queue/ArrayDeque
3. If BFS (breadth-first search) — queue, not stack

LSP Violation

LSP (Liskov Substitution Principle) — subclass must be substitutable by base class. Stack extends Vector violates this: Vector allows get(index), which breaks LIFO semantics.

Stack extends Vector
  → Stack "is a" list
  → But can insert in middle: stack.add(0, x)
  → Breaks stack encapsulation!

ArrayDeque implements Deque
  → Access only via push/pop/peek
  → Cannot break LIFO semantics

Exception Contracts

// java.util.Stack:
stack.pop();        // → EmptyStackException

// ArrayDeque:
deque.pop();        // → NoSuchElementException

// During refactoring: catch correct type!

Concurrency

// If thread-safe stack needed:

// ❌ Stack (slow, coarse-grained lock)
Stack<String> stack = new Stack<>();

// ✅ ConcurrentLinkedDeque (lock-free)
Deque<String> stack = new ConcurrentLinkedDeque<>();

// ✅ synchronized Deque
Deque<String> stack = Collections.synchronizedDeque(new ArrayDeque<>());

Production Experience

Real case: Stack → ArrayDeque

• Expression parser: Stack
• Lock contention: 60% time
• Solution: ArrayDeque
• Result: +250% throughput

(Based on internal benchmarks. Your results will depend on load, JVM and CPU.)

Best Practices

1. DO NOT use java.util.Stack
2. ArrayDeque — for stack in 99% cases
3. ConcurrentLinkedDeque — for thread-safe
4. Deque interface in signatures, not implementation
5. push/pop/peek — standard methods
6. Inheritance from Vector = architectural mistake

Summary for Senior

• Stack = legacy, extends Vector, synchronized
• ArrayDeque = correct replacement (faster, less memory)
• LSP Violation = Stack can be used as list
• Lock-free = ConcurrentLinkedDeque for concurrency
• Exceptions = EmptyStackException vs NoSuchElementException
• NEVER use java.util.Stack in new code

---

🎯 Interview Cheat Sheet

Must know:

• Stack = LIFO (Last In, First Out), push/pop/peek — main operations
• java.util.Stack is legacy — extends Vector, all methods synchronized, LSP violation
• ArrayDeque — correct replacement for stack in 99% cases (faster, less memory, no synchronization)
• LSP Violation: Stack extends Vector → can call get(index), breaking LIFO semantics
• Exception contracts: Stack.pop() → EmptyStackException, ArrayDeque.pop() → NoSuchElementException
• Use Cases: Undo/Redo, call stack, bracket parsing, DFS (depth-first traversal)
• Thread-safe: ConcurrentLinkedDeque (lock-free) or Collections.synchronizedDeque
• Real case: Stack → ArrayDeque replacement gave +250% throughput in parser

Common follow-up questions:

• Why is java.util.Stack bad? — Inherits from Vector: synchronized (slow) + can break LIFO via get(index)
• How is ArrayDeque better than Stack? — No synchronization, less memory, cannot break LIFO semantics
• How to make thread-safe stack? — ConcurrentLinkedDeque (lock-free) or Collections.synchronizedDeque(new ArrayDeque<>())
• When NOT to use stack? — If random access needed (List) or FIFO processing (Queue)

Red flags (NOT to say):

• ❌ “java.util.Stack — decent choice” — it’s legacy, use ArrayDeque
• ❌ “Stack fully encapsulates LIFO” — no, can call get(index) via Vector inheritance
• ❌ “Synchronized = thread-safe stack” — coarse-grained lock kills parallelism, use lock-free
• ❌ “Stack and Queue are interchangeable” — LIFO vs FIFO, different semantics

Related topics:

• [[What is Vector and how does it differ from ArrayList]]
• [[What is Queue and what implementations exist]]
• [[What is Deque]]
• [[What are the main Collection Framework interfaces]]