Stacks
LIFO ordering for tracking nested structure — matching parentheses, undo history, and monotonic sequences.
Try answering in your head first, then click a question to check the model answer.
Q1.Walk through how a stack validates balanced parentheses in a string.(show answer)
Scan the string left to right. On an opening bracket, push it. On a closing bracket, check the top of the stack: if it's the matching opening bracket, pop it; otherwise (mismatch or empty stack), the string is invalid. At the end, the string is valid only if the stack is empty — every opener had a matching, correctly-nested closer.
Q2.Why is a stack the natural data structure for this problem instead of, say, a queue?(show answer)
Balanced brackets nest — the most recently opened bracket must be the next one closed (LIFO order). A stack's last-in-first-out property directly matches this nesting rule: the top of the stack is always the innermost still-open bracket, which is exactly what needs to be checked against the next closing bracket encountered. A queue's FIFO order wouldn't track nesting correctly.
Q3.Explain the monotonic stack technique for the "next greater element" problem.(show answer)
Maintain a stack of indices whose corresponding values are in decreasing order. For each new element, pop any stack elements smaller than it (that new element is their "next greater"), then push the current index. Each index is pushed and popped at most once, so the whole scan runs in O(n) total, versus the naive O(n²) of scanning forward from every index.
Q4.How does the call stack relate to recursion, and why can deep recursion cause a stack overflow?(show answer)
Every recursive call pushes a new stack frame (holding local variables and the return address) onto the program's call stack, and returning pops it off — this is literally a stack data structure managed by the runtime. If recursion goes too deep (e.g. no base case, or a very large input processed recursively without tail-call optimization), the call stack can exceed its allocated memory, causing a stack overflow — which is why very deep recursive algorithms are sometimes rewritten iteratively with an explicit stack instead.