Stack Discipline

Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.

stack = []
stack.append(x)
stack.pop()

Bracket matching is the classic stack application. Must be instant for interview warm-ups.

match = {'(': ')', '[': ']', '{': '}'}
stack = []
for c in s:
    if c in match:
        stack.append(match[c])
    elif not stack or stack.pop() != c:
        return False
return not stack

Maintaining a parallel min stack gives O(1) getMin. Classic design problem.

self.stack.append(val)
self.min_stack.append(
    min(val, self.min_stack[-1] if self.min_stack else val)
)

Stack-based expression evaluation is the foundation for calculator and RPN problems.

for tok in tokens:
    if tok.lstrip('-').isdigit():
        stack.append(int(tok))
    else:
        b, a = stack.pop(), stack.pop()
        if tok == '+': stack.append(a + b)
        elif tok == '-': stack.append(a - b)
        elif tok == '*': stack.append(a * b)
        elif tok == '/': stack.append(int(a / b))

Monotonic stacks find next-greater/smaller elements in O(n). Key for histogram and temperature problems.

stack = []
for x in a:
    while stack and stack[-1] >= x:
        stack.pop()
    stack.append(x)

Next-greater-element uses a decreasing stack. Shows up in stock span and temperature problems.

result = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
    while stack and stack[-1] <= a[i]:
        stack.pop()
    if stack:
        result[i] = stack[-1]
    stack.append(a[i])

Using a stack to reverse order is the intuition behind reversing linked lists and strings.

stack = []
for x in a:
    stack.append(x)
reversed_a = []
while stack:
    reversed_a.append(stack.pop())

Stack-based evaluation pops two operands per operator. Handles all four arithmetic ops.

st = []
for t in tokens:
    if t in '+-*/':
        b, a = st.pop(), st.pop()
        st.append(int(eval(f'{a}{t}{b}')))
    else:
        st.append(int(t))

Decreasing stack resolves waiting days when a warmer temperature arrives.

res = [0] * len(t)
st = []
for i, v in enumerate(t):
    while st and t[st[-1]] < v:
        j = st.pop()
        res[j] = i - j
    st.append(i)

RPN evaluation: numbers push, operators pop two and push result. Note: pop order is b, a (right operand first).

stack = []
for tok in tokens:
    if tok in '+-*/':
        b, a = stack.pop(), stack.pop()
        if tok == '+': stack.append(a + b)
        elif tok == '-': stack.append(a - b)
        elif tok == '*': stack.append(a * b)
        else: stack.append(int(a / b))
    else:
        stack.append(int(tok))