package com.thealgorithms.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);
    }
}