import java.util.*;

public class Stacks {
   /* static class Stack{
        static ArrayList<Integer> list= new ArrayList<>();
        public boolean isEmpty(ArrayList<Integer> list){
            return list.size()==0;
        }
        public int pop(ArrayList<Integer> list){
            if(isEmpty(list)) return -1;
            int x= list.get(list.size()-1);
            list.remove(list.size()-1);
            return x;
        }
        public void push(ArrayList<Integer> list, int n){
            list.add(n);
            return;
        }
        public int peek(ArrayList<Integer> list){
            if(isEmpty(list)) return -1;
            return list.get(list.size()-1);
        }
    }*/
   public static Stack bottomPush(Stack s,int n){
        if(s.isEmpty()) {
            s.push(n);
            return s;
        }
        int x= (int) s.pop();
        bottomPush(s,n);
        s.push(x);
        return  s;
    }

    public static String stringReverse(String str){
        Stack<Character> s= new Stack<>();
        int i=0;
        StringBuilder sb=new StringBuilder("");
        while(i<str.length()){
            s.push(str.charAt(i));
            i++;
        }
        i=0;
        while(i<s.size()){
            sb.append(s.pop());
        }
        return sb.toString();
    }

    public static Stack reverseStack(Stack s){
        if(s.size()==0) return s;
        int x= (int) s.pop();
        reverseStack(s);
        bottomPush(s,x);
        return s;
    }
    public static void main(String[] args){
        Stack <Integer> s=new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s);
        System.out.println(stringReverse("a"));
        System.out.println(reverseStack(s));
    }
}