Knowledge Guide
Home › DSA

Stack

Step 7 in the DSA path · 9 concepts · 13 problems

0 / 22 complete

📘 Learn Stack from zero

A stack is a LIFO (last-in, first-out) structure: you push onto the top and pop from the top, both in O(1). The pattern shines whenever the most recent unresolved item is the one you must handle next — nested or "matching" structure. Trigger to reach for a stack: you see balanced/nested symbols (brackets, tags), you must undo or backtrack the latest action, you're parsing expressions (RPN), or you need the nearest previous/next element (monotonic stack). Canonical example below: Valid Parentheses — given s = "([{}])" mixed with a failing case, decide if every bracket is correctly closed by its matching opener in the right order.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Setup & the rule
s = ( [ { } ] )
idx 0 1 2 3 4 5

stack: [ ]   (empty, grows to the right ->)
map: ) -> (   ] -> [   } -> {

We scan left to right. On an opener we push it; on a closer we check the stack top. The stack holds "openers still waiting to be matched." This is safe because the last opener pushed is exactly the one that must be closed first — the LIFO order mirrors how brackets nest.

Step 2 — Read '(' push it
s = ( [ { } ] )
    ^ i=0  '('  (opener)

stack: [ ( ]
         ^ top

Char ( is an opener, so we push('('). We record it as an outstanding obligation; nothing to validate yet. The newest opener sits on top, ready to be the first one we try to match.

Step 3 — Read '[' push it
s = ( [ { } ] )
      ^ i=1  '['  (opener)

stack: [ ( [ ]
           ^ top

Another opener, so push('['). The stack now reads bottom-to-top as ( [, encoding the nesting depth so far. Because [ is on top, it must be closed before the ( beneath it — which is exactly correct nesting.

Step 4 — Read '{' push it
s = ( [ { } ] )
        ^ i=2  '{'  (opener)

stack: [ ( [ { ]
             ^ top

Third opener, so push('{'). Stack bottom-to-top is ( [ {, the full open nesting. We have made no matching decisions yet — pushing is always safe for openers since their match is deferred until the corresponding closer appears.

Step 5 — Read '}' top matches, pop
s = ( [ { } ] )
          ^ i=3  '}'  (closer)

map['}'] = '{' ,  top = '{'  -> MATCH

stack: [ ( [ ]   (popped '{')
           ^ top

} is a closer. We compare map['}']='{' with the current top { — they match, so we pop(). This is safe: the most recently opened bracket is the one being closed, satisfying LIFO. If the top had differed (or the stack were empty), we'd return false immediately.

Step 6 — Read ']' top matches, pop
s = ( [ { } ] )
            ^ i=4  ']'  (closer)

map[']'] = '[' ,  top = '['  -> MATCH

stack: [ ( ]   (popped '[')
         ^ top

] expects [ and the top is [ — match, so pop(). We are unwinding the nesting in reverse open-order, exactly as LIFO guarantees. One opener (() remains outstanding.

Step 7 — Read ')' top matches, pop -> empty
s = ( [ { } ] )
              ^ i=5  ')'  (closer)

map[')'] = '(' ,  top = '('  -> MATCH

stack: [ ]   (empty)

End of string + stack empty -> return TRUE

) expects ( and the top is ( — match, pop(). After the last char the stack is empty, meaning every opener found its closer in the correct order, so we return true. A non-empty stack at the end would mean unclosed openers -> false.

Step 8 — Why a mismatch fails fast ("(]")
s = ( ]
      ^ i=1  ']'  (closer)

stack: [ ( ]   top = '('
map[']'] = '['  !=  '('  -> MISMATCH

return FALSE  (no need to scan further)

Contrast case: with "(]" we push (, then see ] whose required opener [ does not equal the top (. We return false at once. The stack lets us detect the wrong closer the instant it appears — overall the algorithm is O(n) time and O(n) space.

🎯 Guided practice

  1. Easy — Reverse a String using a stack. Given "abc", return "cba".

    Pattern: a stack naturally reverses order, because the first char pushed comes out last. Steps: (1) Push every character: stack becomes bottom→top a, b, c. (2) Pop until empty, appending each popped char to the result: pop c, then b, then a → "cba". (3) Return the result. Time O(n), space O(n). Why a stack fits: the LIFO order is the reversal — no index arithmetic needed. (The same buffer idea drives Decimal to Binary: push each n % 2 while halving n, then pop to read the bits most-significant-first.)

  2. Medium — Next Greater Element (monotonic stack). For each element, find the first element to its right that is strictly greater; output -1 if none. Input [2, 1, 2, 4].

    Pattern: a monotonic decreasing stack of indices. We keep indices whose "next greater" is still unknown; the current element resolves any smaller pending ones. Steps (each index is pushed and popped once → O(n)):

    • i=0, val 2: stack empty, push 0. Stack(idx): [0]
    • i=1, val 1: 1 is not greater than nums[0]=2, so push. Stack: [0,1]
    • i=2, val 2: 2 > nums[1]=1 → pop index 1, set ans[1]=2. Now 2 is not > nums[0]=2 (strict), stop. Push 2. Stack: [0,2]
    • i=3, val 4: 4 > nums[2]=2 → pop 2, ans[2]=4. 4 > nums[0]=2 → pop 0, ans[0]=4. Stack empty, push 3. Stack: [3]
    • End: index 3 never resolved → ans[3]=-1. Result: [4, 2, 4, -1]

    Why it works: the current value resolves the "next greater" for every smaller element still waiting on the stack, in one pass. Because the comparison is strict (>), an equal neighbor does not pop — that is why ans[0] stayed unresolved at i=2. Storing indices (not values) lets you write into the answer array at the right position and also lets you compute distances — the same template solves Daily Temperatures (push days, pop when a strictly warmer day arrives, and record i - j, the gap in days, rather than the temperature itself).

✨ Added by the guide — work these before the full problem set.

Lessons in this topic