PushBottom.java

import java.util.*;

public class PushBottom {

    public static void pushBottom(Stack <Integer> s,int target){
        Stack <Integer> st = new Stack<>();

        while(!s.isEmpty()){
            st.push(s.pop());
        }

        s.push(target);

        while(!st.isEmpty()){
            s.push(st.pop());
        }
    }

    public static void pushBottomOptimised(Stack <Integer> s , int data){
        if(s.isEmpty()){
            s.push(data);
            return;
        }
        int top = s.pop();
        pushBottom(s, data);
        s.push(top);
    }
    public static void main(String args[]){
        Stack <Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        //pushBottom(s, 0);
        pushBottomOptimised(s, 5);
        while(!s.isEmpty()){
            System.out.println(s.peek());
            s.pop();
        }
    }    
}