@@ -0,0 +1,1844 @@
+package test;%0A%0A/*%0Aval stack = new java.util.Stack%5BInteger%5D()%0Astack.push(6)%0Astack.push(5)%0Astack.push(3)%0Astack.push(1)%0Astack.push(4)%0Astack.push(2)%0A%0Ascala%3E stack%0Ares17: java.util.Stack%5BInteger%5D = %5B6, 5, 3, 1, 4, 2%5D%0A%0Ascala%3E test.Test.sortStackBetter(stack)%0A%0Ascala%3E stack%0Ares19: java.util.Stack%5BInteger%5D = %5B6, 5, 4, 3, 2, 1%5D%0A*/%0Aimport java.util.Stack;%0A%0Apublic class Test %7B%0A  private static void sortedPush(Stack%3CInteger%3E stack, int elem) %7B%0A    Stack%3CInteger%3E tmp = new Stack%3CInteger%3E();%0A    while (!stack.isEmpty() && stack.peek() %3C elem) %7B%0A      tmp.push(stack.pop());%0A    %7D%0A    stack.push(elem);%0A    while (!tmp.isEmpty()) %7B%0A      stack.push(tmp.pop());%0A    %7D%0A  %7D%0A%0A  // Uses O(n%5E2) time and O(n) of space, but it uses 2 stacks at any given moment, which is%0A  // more than allowed by question, see better solution below%0A  public static void sortStackNaive(Stack%3CInteger%3E stack) %7B%0A    Stack%3CInteger%3E tmp = new Stack%3CInteger%3E();%0A    while (!stack.isEmpty()) %7B%0A      tmp.push(stack.pop());%0A    %7D%0A%0A    while (!tmp.isEmpty()) %7B%0A      sortedPush(stack, tmp.pop());%0A    %7D%0A  %7D%0A%0A  // Runs in O(n%5E2) time and O(n) space and uses only one additional stack%0A  public static void sortStackBetter(Stack%3CInteger%3E stack) %7B%0A    Stack%3CInteger%3E tmp = new Stack%3CInteger%3E();%0A    while (!stack.isEmpty()) %7B%0A      int elem = stack.pop();%0A      int count = 0;%0A      while (!tmp.isEmpty() && tmp.peek() %3E elem) %7B%0A        stack.push(tmp.pop());%0A        count++;%0A      %7D%0A      tmp.push(elem);%0A      while (count %3E 0) %7B%0A        tmp.push(stack.pop());%0A        count--;%0A      %7D%0A    %7D%0A%0A    // tmp stack has elements in decreasing order (largest element on top)%0A    // shift them back into stack to have smallest element on top%0A    // we could avoid this by pushing elements in reversed order and returning tmp%0A    while (!tmp.isEmpty()) %7B%0A      stack.push(tmp.pop());%0A    %7D%0A  %7D%0A%7D%0A

add sort-stack solution