Reverse a stack using recursion

The problem, simply

You get a stack, a pile where you can only touch the top: push puts something on top, pop takes the top off, peek looks at it, and isEmpty checks if the pile is empty. Reverse it, so the bottom item ends on top.

The catch: no other stack, queue, array or list is allowed. You may only use recursion, functions that call themselves. Their waiting calls are allowed to remember one item each.

A story to remember it

Picture it

Examples

Way 1: the simple way

If any helper box were allowed, this is easy. Pop everything into a queue. The queue now holds the items top first. Push them back in that same order, and the old top ends up at the bottom.

1. While the stack is not empty, pop and add to the back of a queue.
2. While the queue is not empty, take from the front and push.

import java.util.*;

class Solution {
    public void reverse(Deque<Integer> stack) {
        Queue<Integer> line = new ArrayDeque<>();
        while (!stack.isEmpty()) line.offer(stack.pop());   // top comes out first
        while (!line.isEmpty()) stack.push(line.poll());    // and goes back in first, at the bottom
    }
}

How long it takes: every item moves twice, O(n). Extra room: the queue, O(n). Fast, but it breaks the rule: it uses another structure.

Way 2: the clever way

Use two recursive functions.

insertAtBottom(x) puts x under everything:

1. If the stack is empty, push x. Done.
2. Otherwise pop the top and hold it, call insertAtBottom(x) on the smaller stack, then push the held item back.

reverse() flips the stack:

1. If the stack is empty, stop.
2. Pop the top and hold it, call reverse() on the smaller stack, then insertAtBottom(held).

Why it works: after the inner reverse(), the rest is upside down. The item we held was above all of them, so in the flipped stack it belongs below all of them.

import java.util.*;

class Solution {
    public void reverse(Deque<Integer> stack) {
        if (stack.isEmpty()) return;
        int top = stack.pop();           // hold the top plate
        reverse(stack);                  // flip the rest
        insertAtBottom(stack, top);      // the old top belongs at the very bottom
    }

    private void insertAtBottom(Deque<Integer> stack, int x) {
        if (stack.isEmpty()) {
            stack.push(x);               // nothing in the way: x is the bottom
            return;
        }
        int held = stack.pop();          // lift one plate out of the way
        insertAtBottom(stack, x);
        stack.push(held);                // put it back on top
    }
}

How long it takes: reverse runs n times, and the kth insertAtBottom lifts k - 1 plates, so the total is 0 + 1 + ... + (n - 1), about n^2 / 2, which is O(n^2). Extra room: at the deepest point about n calls wait on the call stack, O(n). That is the price of the "no other structure" rule.

Watch out for

• Pushing the held item back before the inner reverse() call. The stack never gets smaller and the calls never end.
• Forgetting that the call stack is real memory. A stack of 100,000 items needs 100,000 waiting calls, which can throw StackOverflowError in Java.
• java.util.Stack works too, but Deque with push and pop is the modern choice. Both put new items on top.

What interviewers ask next

• Sort a stack with recursion. Same shape, but instead of inserting at the bottom, insert the held item where it belongs in the sorted stack.
• Insert at the bottom of a stack, by itself. That is insertAtBottom alone, O(n) time and O(n) call stack.
• Reverse a queue with recursion. Easier: take the front, reverse the rest, then add it at the back. Only O(n), because a queue already lets you add at the far end.
• Can you reverse a stack in O(n) with no extra structure? If the stack is built as a linked list you own, yes: reverse the arrows of the list. With only push and pop, no.

Remember this

Grown-up words: the plate tower is a stack, the helpers holding plates are frames on the call stack, insertAtBottom is a recursive helper, and "no other box allowed" means no auxiliary data structure.