package DataStructures.Stacks;

import java.util.Scanner;
import java.util.Stack;

/**
 * Reversal of a stack using recursion. 
 *
 * @author Ishika Agarwal, 2021
 */

public class ReverseStack {

 public static void main(String args[]){

 Scanner sc = new Scanner(System.in);
 System.out.println("Enter the number of elements you wish to insert in the stack");
 int n = sc.nextInt();
 int i;
 Stack<Integer> stack = new Stack<Integer>();
 System.out.println("Enter the stack elements");
 for(i = 0; i < n ; i++)
 stack.push(sc.nextInt());
 sc.close();
 reverseStack(stack);
 System.out.println("The reversed stack is:");
 while(!stack.isEmpty()){
 System.out.print(stack.peek()+",");
 stack.pop();
 }

 }

 private static void reverseStack(Stack<Integer> stack) {
 if(stack.isEmpty()){
 return;
 }

 //Store the topmost element
 int element = stack.peek();
 //Remove the topmost element
 stack.pop();

 //Reverse the stack for the leftover elements
 reverseStack(stack);

 //Insert the topmost element to the bottom of the stack
 insertAtBottom(stack,element);

 }

 private static void insertAtBottom(Stack<Integer> stack, int element) {
 
 if(stack.isEmpty()){
 //When stack is empty, insert the element so it will be present at the bottom of the stack
 stack.push(element);
 return;
 }

 int ele = stack.peek();
 /*Keep popping elements till stack becomes empty. Push the elements once the topmost element has
 moved to the bottom of the stack.
 */
 stack.pop();
 insertAtBottom(stack, element);

 stack.push(ele);
 }
 
}