Stack Computation

Stack Computation: The Magic Plate Dispenser 🍽️

Imagine a stack of plates at a buffet. You can only take the top plate, and new plates go on top. That’s exactly how a Stack works in programming!

The Big Picture

A Stack is like a stack of plates:

• Push = Put a plate on top
• Pop = Take the top plate off
• Peek = Look at the top plate (without removing it)

Rule: Last In, First Out (LIFO) — the last plate you put in is the first one you take out!

graph TD
    A["Push 5"] --> B["Stack: 5"]
    B --> C["Push 3"]
    C --> D["Stack: 5, 3"]
    D --> E["Pop"]
    E --> F["Stack: 5"]
    F --> G["Returns: 3"]

1. Min Stack: The Clever Helper 🧠

What’s the Problem?

You want a stack that can tell you the smallest number inside it — instantly! Not by searching through everything, but in one quick peek.

The Story

Imagine you’re stacking toy blocks with numbers on them. Your little sister keeps asking, “What’s the smallest number in your tower?”

Instead of looking at every block (slow!), you keep a secret notebook. Every time you add a block, you write down the smallest number so far. Now you can answer instantly!

How It Works

class MinStack:
    def __init__(self):
        self.stack = []      # Regular plates
        self.min_stack = []  # Secret notebook

    def push(self, val):
        self.stack.append(val)
        # Write the smallest so far
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(
                min(val, self.min_stack[-1])
            )

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def getMin(self):
        return self.min_stack[-1]

Example Walk-Through

Magic: We always know the minimum in O(1) time!

2. Expression Parsing and Evaluation 🧮

What’s the Problem?

How does a calculator understand "3 + 5 * 2"? It needs to know that multiplication comes before addition!

The Story

Think of a chef reading a recipe. Some steps must happen first (like preheating the oven) before others (like baking). A stack helps the chef remember what to do and in what order!

The Secret: Two Stacks

1. Number Stack — holds the ingredients (numbers)
2. Operator Stack — holds the cooking instructions (+, -, *, /)

How It Works

def evaluate(expression):
    nums = []
    ops = []

    precedence = {'+': 1, '-': 1,
                  '*': 2, '/': 2}

    def apply_op():
        b = nums.pop()
        a = nums.pop()
        op = ops.pop()
        if op == '+': nums.append(a + b)
        elif op == '-': nums.append(a - b)
        elif op == '*': nums.append(a * b)
        elif op == '/': nums.append(a // b)

    i = 0
    while i < len(expression):
        if expression[i].isdigit():
            num = 0
            while i < len(expression) \
                  and expression[i].isdigit():
                num = num * 10 + int(expression[i])
                i += 1
            nums.append(num)
            continue

        if expression[i] in precedence:
            while ops and ops[-1] in precedence \
                  and precedence[ops[-1]] >= \
                      precedence[expression[i]]:
                apply_op()
            ops.append(expression[i])
        i += 1

    while ops:
        apply_op()

    return nums[0]

Example: "3+5*2"

Answer: 13 ✓

3. Basic Calculator 🔢

What’s the Problem?

Now we add parentheses! How do you solve "(1+2)*3"?

The Story

Parentheses are like VIP sections at a party. Everything inside the VIP rope gets calculated first, no matter what!

The Trick

When you see (, save your current work on a stack. When you see ), finish the VIP calculation and add it back!

def calculate(s):
    stack = []
    num = 0
    sign = 1
    result = 0

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)

        elif char == '+':
            result += sign * num
            num = 0
            sign = 1

        elif char == '-':
            result += sign * num
            num = 0
            sign = -1

        elif char == '(':
            # Save current work
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1

        elif char == ')':
            result += sign * num
            num = 0
            # Get saved work back
            result *= stack.pop()  # sign
            result += stack.pop()  # prev result

    return result + sign * num

Example: "(1+2)*3"

4. Decode String 🔓

What’s the Problem?

Given "3[a2[c]]", what’s the decoded string?

Answer: "accaccacc"

The Story

It’s like a magic copying machine! The number tells you how many copies to make. Brackets show what to copy.

The Trick

Use a stack to remember:

• What letters you had before the [
• How many copies you need

def decodeString(s):
    stack = []
    current_string = ""
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 \
                         + int(char)

        elif char == '[':
            # Save current work
            stack.append(current_string)
            stack.append(current_num)
            current_string = ""
            current_num = 0

        elif char == ']':
            # Time to copy!
            num = stack.pop()
            prev_string = stack.pop()
            current_string = prev_string \
                           + current_string * num

        else:
            current_string += char

    return current_string

Example: "3[a2[c]]"

Magic: 2[c] → cc, then a + cc = acc, then 3[acc] → accaccacc!

5. Asteroid Collision 💥

What’s the Problem?

Asteroids fly in a row. Positive = moving right →, Negative = moving left ←. When they meet, the smaller one explodes! Same size? Both explode!

The Story

Imagine bumper cars! Cars going the same direction never crash. But when one going right meets one going left — BOOM! The bigger car wins!

The Rules

1. Same direction → No crash
2. Different direction → Bigger wins (or both explode if equal)
3. Positive going right, negative going left

def asteroidCollision(asteroids):
    stack = []

    for ast in asteroids:
        alive = True

        # Collision possible: stack has right-mover
        # and current goes left
        while stack and ast < 0 and stack[-1] > 0:
            if stack[-1] < -ast:
                # Current wins, pop stack
                stack.pop()
                continue
            elif stack[-1] == -ast:
                # Both explode
                stack.pop()
                alive = False
                break
            else:
                # Stack wins
                alive = False
                break

        if alive:
            stack.append(ast)

    return stack

Example: [5, 10, -5]

Result: [5, 10]

Example: [8, -8]

Result: []

6. Remove K Digits 🔢✂️

What’s the Problem?

Given a number string and k, remove k digits to make the smallest possible number.

The Story

You’re building the shortest, smallest number possible. Keep removing digits that are “too big” compared to what comes next!

The Greedy Trick

If a digit is bigger than the next one, remove it! This makes the number smaller.

def removeKdigits(num, k):
    stack = []

    for digit in num:
        # Remove bigger digits from stack
        while k > 0 and stack \
              and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # Remove remaining from end if needed
    while k > 0:
        stack.pop()
        k -= 1

    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

Example: num = "1432219", k = 3

Result: "1219" ✓

Quick Summary

graph LR
    A["Stack Computation"] --> B["Min Stack"]
    A --> C["Expression Parsing"]
    A --> D["Basic Calculator"]
    A --> E["Decode String"]
    A --> F["Asteroid Collision"]
    A --> G["Remove K Digits"]

    B --> B1["Track minimum<br>with helper stack"]
    C --> C1["Two stacks:<br>nums & operators"]
    D --> D1["Save state at<br>parentheses"]
    E --> E1["Stack saves<br>previous context"]
    F --> F1["Compare & destroy<br>smaller asteroids"]
    G --> G1["Greedily remove<br>bigger digits"]

Key Patterns to Remember

You’ve Got This! 🚀

Stack problems follow a pattern:

1. When to push? New element arrives
2. When to pop? Some condition triggers processing
3. What to track? The “state” you need to remember

Practice these 6 problems, and you’ll see stacks everywhere! They’re not scary — they’re just helpful plate dispensers keeping track of your data.

Remember: Last In, First Out. The newest plate is always on top! 🍽️