package stacks_queues;

import java.util.Stack;

public class SortStack {


    private static Stack<Integer> sort(Stack<Integer> stack) {
        // empty stack is already sorted
        if (stack.empty()) {
            return stack;
        }

        // empty stack is  sorted
        Stack<Integer> helperStack = new Stack<>();

        // stack with one element is sorted
        helperStack.push(stack.pop());

        while (!stack.empty()) {
            // the top element from original stack
            int remembered = stack.peek();

            // if the top of the input stack is lesser than top of our helper stack, we can move it to the helper stack
            // and as result the helper stack remains sorted (the higher we are the smaller the element is)
            if (remembered < helperStack.peek()) {
                helperStack.push(remembered);
            } else {
                // If the top (remembered) of the input stack is greater than the top of helper stack, we must make an effort to
                // place the remembered value in the such position in the helper stack that will preserve its order.
                // We first move elements lesser than `remembered` to the original stack, then push the remembered value to the helper stack
                // and finally move all the lesser elements back to the helper stack, therefore preserving the order.
                while (remembered > helperStack.peek()) {
                    stack.push(helperStack.pop());
                }
                helperStack.push(remembered);

                while (stack.peek() != remembered) {
                    helperStack.push(stack.pop());
                }
            }
            // at this point the `remembered` value is still present at the top of the original stack
            stack.pop();
        }
        return helperStack;
    }

    public static void main(String[] args) {
        Stack<Integer> toBeSorted = new Stack<>();

        toBeSorted.push(3);
        toBeSorted.push(-2);
        toBeSorted.push(1);
        toBeSorted.push(4);
        toBeSorted.push(0);
        toBeSorted.push(-3);
        toBeSorted.push(-5);
        toBeSorted.push(-2);
        toBeSorted.push(6);

        Stack<Integer> sorted = sort(toBeSorted);

        System.out.println(sorted);
    }
}