📥

Simple Stack

Push elements onto the stack; when a closing bracket arrives, pop the top and verify it matches. LIFO guarantees correct nesting order. If the stack is empty on a close or non-empty after scan — invalid.

LIFO Bracket Matching Expression Eval Time O(n) Space O(n)

📋 When to Use

Match brackets / parentheses — validate nesting and ordering
Evaluate postfix expressions — push operands, pop on operator
Maintain min/max in O(1) — auxiliary stack tracks running extremum
Support undo last operation — push state, pop to revert
Simulate DFS / recursion — explicit stack replaces call stack

💡 Key insight: LIFO order means the most recently opened bracket is always on top — exactly what you need to verify correct nesting when a closing bracket arrives.

⚡ Complexity

Time

O(n)

Space

O(n)

Each character is pushed at most once and popped at most once — two passes over n chars = O(n) time. In the worst case all opening brackets are pushed before any closing bracket, consuming O(n) space.

Problem Valid Parentheses: s = ({[]}) — scan left to right. Opening brackets ( { [ are pushed onto the stack. Closing brackets ) } ] trigger a pop: if the popped bracket matches the expected closer, continue; otherwise invalid. Stack empty at end = ✅ VALID.

Step 1 / —

📖 Scan

📥 Push

🔍 Pop+Match

✅ Valid!

s = "({[]}})" — characters to process:

Stack (top → bottom)

empty

Match Result

Match result appears when a closing bracket is processed

Click ▶ Play or Next ▶ to begin

Deque<Character> stack = new ArrayDeque<>();

Simple Stack — Pattern SkeletonJAVA

// Simple Stack — Bracket Matching ────────────────────────────────
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (isOpen(c)) {
        stack.push(c);          // push opening bracket
    } else {
        if (stack.isEmpty()) return false;
        char top = stack.pop(); // pop and verify
        if (!matches(top, c)) return false;
    }
}
return stack.isEmpty();         // leftover = unmatched open

🎯 Practice Problems

#20Valid ParenthesesEasy #150Evaluate Reverse Polish NotationMedium #155Min StackMedium #224Basic CalculatorHard