public class StackSorting {
    public static void main(String[] args) {
        StackSorting ss = new StackSorting();
        Deque<Integer> stack = new LinkedList<>();
        stack.offerFirst(2);
        stack.offerFirst(1);
        stack.offerFirst(3);
        stack.offerFirst(1);
        stack.offerFirst(3);
        Deque<Integer> helper = ss.stackSorting(stack);
        System.out.println("result top is largest" + Arrays.toString(helper.toArray()));
    }
    // System.out.println("result top is largest" + Arrays.toString(helper.toArray()));
    public Deque<Integer> stackSorting(Deque<Integer> stack) {// stack unsorted
        Deque<Integer> helper = new LinkedList<>(); // helper sorted
        //* int size = stack.size();
        //* int sortedSize = 0;
        int min = Integer.MAX_VALUE;
        int count = 0; // for duplication
        while (!stack.isEmpty()) {
        //* while (sortedsize < size) {
            // stack --> helper find min value
            while (!stack.isEmpty()) {
                int tmp = stack.pollFirst();
                min = Math.min(min, tmp);
                helper.offerFirst(tmp);
            }
            // helper --> stack except the min values
            // 2 1 3 1 3
            while (helper.peekFirst() != null && helper.peekFirst() >= min) {
            // while (helper.size() > sortedSize) {
                int tmp = helper.pollFirst();
                if (tmp != min) {
                    stack.offerFirst(tmp);
                } else {
                    count++;
                }
            }
            // push min values to helper
            for (int i = 0; i < count; i++) {
                helper.offerFirst(min);
            }
            // sortedSize = helper.size();
            min = Integer.MAX_VALUE;
            count = 0;
        }
        return helper;
    }
}