Reverse a stack using recursion

Approach

• Create a new empty stack.
• Create function to insert_at_bottom in which we will check if the stack is empty if its empty just push the element else store the top element in a variable pop the element and call the insert at bottom function recursively so that stack will be empty and  then push the value stored in the variable in the stack.
• In Reverse function We will store the top element in the variable x using peek function then pop the element then call reverse function recursively so  that all the elements are popped and the top most element is stored in the variable x after  that we will call insert at bottom function and insert the value of x at the bottom.

 

Diagram

 

Java Code

import java.util.Stack;

class ReverseUsingRecursion {

	Stack<Character> stack = new Stack<>();

	public void insertAtBottom(char x){
		if (stack.isEmpty()){
			stack.push(x);
		}
		else {
			char a = stack.peek();
			stack.pop();
			insertAtBottom(x);
			stack.push(a);
		}
    }

	public void reverse(){
		if (stack.size() > 0) {
			char x = stack.peek();
			stack.pop();
			reverse();
			insertAtBottom(x);
		}
	}

	public static void main(String[] args){

		ReverseUsingRecursion reverseStack = new ReverseUsingRecursion();
		reverseStack.stack.push('1');
		reverseStack.stack.push('2');
		reverseStack.stack.push('3');
		reverseStack.stack.push('4');

		System.out.println("Original Stack");
		System.out.println(reverseStack.stack);

		reverseStack.reverse();

		System.out.println("Reversed Stack");
		System.out.println(reverseStack.stack);
	}
}

Output

Original Stack
[1, 2, 3, 4]
Reversed Stack
[4, 3, 2, 1]

### Complexity Analysis * **Time Complexity**: O(N) where N is the number of elements in the stack. * **Space Complexity**: O(N) for the recursive call stack.