Recursive Stack Manipulation

Description

Sort a stack using only push, pop, peek and isEmpty - no array, no second stack. It looks impossible until you notice that recursion already gives you a stack: every pending call holds its local variables. Popping into a local variable and pushing back as the calls return is a stack of popped values for free.

This skill covers the pop, recurse, push-back shape that sorts or reverses a stack with nothing but recursion, and the same save-and-restore idea applied to nested text such as "2[x3[yz]]". It also covers when to trade the call stack for an explicit one.

We'll go from simple to more technical:

1. The pattern: sort a stack by popping, sorting the rest, and inserting in place.
2. A second flavor: nested structure (Decode String) with explicit stacks of saved state.
3. Where save-and-restore shows up (parsers, template engines, nested scopes).
4. What breaks it: unrestored pops, single-digit counts, recursion depth, the sort direction.

The approach

void sort(Deque<Integer> stack) {
    if (stack.isEmpty()) return;
    int top = stack.pop();
    sort(stack);                        // sort everything below first
    insertSorted(stack, top);           // then put this value in its place
}

void insertSorted(Deque<Integer> stack, int val) {
    if (stack.isEmpty() || stack.peek() <= val) {   // largest ends up on top
        stack.push(val);
        return;
    }
    int top = stack.pop();
    insertSorted(stack, val);           // dig below the larger value
    stack.push(top);                    // then restore it on top
}

def sort(stack: list[int]) -> None:               # a list: append / pop / [-1], top at the end
    if not stack:
        return
    top = stack.pop()
    sort(stack)                                   # sort everything below first
    insert_sorted(stack, top)                     # then put this value in its place


def insert_sorted(stack: list[int], val: int) -> None:
    if not stack or stack[-1] <= val:             # largest ends up on top
        stack.append(val)
        return
    top = stack.pop()
    insert_sorted(stack, val)                     # dig below the larger value
    stack.append(top)                             # then restore it on top

Both functions share one shape: pop, recurse on the smaller problem, and push back on the way out. insertSorted must restore what it popped - forgetting stack.push(top) silently drops elements. Each insert may dig through the whole stack, so sorting is O(n^2) time with O(n) recursion depth. Reversing a stack works the same way, with "insert at the bottom" in place of "insert in order".

A second flavor: nested structure

Decoding "2[x3[yz]]" into "xyzyzyzxyzyzyz" needs the same save-and-restore: when a [ opens, remember the text built so far and the repeat count; when ] closes, repeat the inner text and append it to the saved outer text.

String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> outer = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');             // counts can have several digits: "12[ab]"
        } else if (c == '[') {
            counts.push(k);
            outer.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            String inner = cur.toString();
            cur = outer.pop();
            cur.append(inner.repeat(counts.pop()));
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

def decode_string(s: str) -> str:
    counts, outer = [], []
    cur = []                                      # pieces of the current text
    k = 0
    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)                   # counts can have several digits: "12[ab]"
        elif c == "[":
            counts.append(k)
            outer.append(cur)
            cur = []
            k = 0
        elif c == "]":
            inner = "".join(cur)
            cur = outer.pop()
            cur.append(inner * counts.pop())      # str * int repeats the string
        else:
            cur.append(c)
    return "".join(cur)

The explicit stacks here do what recursion would do (a recursive decoder calls itself at each [ and returns at ]). Reading only one digit at a time turns "10[a]" into a single 'a' repeated 0 times after a '1' - the count must accumulate.

Where you'll see it

Parsers and template engines handle nested constructs (JSON inside JSON, {{#each}} blocks inside blocks) with exactly this save-state-on-open, restore-on-close pattern - either as recursion or an explicit stack. Undoing nested transactions and unwinding nested scopes in interpreters work the same way.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Where are the popped values stored while the recursive sort runs?

2. What goes wrong if insertSorted forgets stack.push(top) after its recursive call?

3. In Decode String, why must the repeat count accumulate digits?

Key takeaways

• Pop, recurse, push back: the call stack stores the popped values.
• Recursive stack sort is O(n^2) time and O(n) depth.
• Nested structure: save the outer state at [, restore and combine at ].
• Accumulate multi-digit counts; watch the recursion depth.