[Google] Reverse a Stack without DS

Question

link

Reverse a stack using recursion. You are not allowed to use loops or data structure, and you can only use the following functions:

isEmpty(S)
push(S)
pop(S)

Solution

Well since we are not allowed to use additional DS or loop, we have to use system stack to help us!

We add a new method: insert at stack bottom. Then we can solve this question recursively. Nice question, and tricky answer!

Code

public void reverse(Stack<Integer> stack) {
    if (stack.isEmpty() || stack.size() == 1) {
        return;
    }
    int top = stack.pop();
    this.reverse(stack);
    this.insertAtBottom(stack, top);
}

private void insertAtBottom(Stack<Integer> stack, int val) {
    if (stack.isEmpty()) {
        stack.push(val);
        return;
    }
    int temp = stack.pop();
    this.insertAtBottom(stack, val);
    stack.push(temp);
}