Reverse a Stack using Recursion

algorithm

Reverse a Stack using Recursion

The code is like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Stack;

// reverse a stack using recursion
// loop constructs such as while or for loops are not allowed
public class ReverseStack {
    public static Stack<Character> stack = new Stack<>();

    // insert a character x at the bottom of the stack
    public static void insertBottom(char x) {
        if(stack.empty()) {
            stack.push(x);
        }else {
            char a = stack.pop();
            insertBottom(x);
            stack.push(a);
        }
    }

    // reverse the given stack using insertAtBottom()
    public static void reverse() {
        if(stack.size() > 0) {
            char x = stack.pop();
            reverse();
            insertBottom(x);
        }
    }

    public static void main(String[] args) {
        stack.push('w');
        stack.push('a');
        stack.push('t');
        stack.push('e');
        stack.push('r');

        System.out.println(stack);

        reverse();
        System.out.println(stack);
    }
}

To solve this problem, we need to make use of two function call stacks, one is for reverse method, and the other is for insertBottom method. The process is like this: https://www.youtube.com/watch?v=5lynUjiYXcU