Sort a stack using Java This is my attempted solution to cracking the coding interview exercise 3.5.  Looking for any feedback on coding style or the algorithm anywhere I can improve really.

The problem specification is as follows.


  Write a program to sort a stack such that the smallest items are on the top.  You can use an additional temp stack, but you may not copy the elements into any other data structure (such as an array).  The stack supports push, pop, peek and isEmpty.


MyStack.java

package problem_2_8;

import java.util.ArrayList;
import java.util.EmptyStackException;

public class MyStack&lt;T extends Comparable&lt;T&gt;&gt; {

    private static class StackNode&lt;T extends Comparable&lt;T&gt;&gt; {
        T data;
        StackNode&lt;T&gt; next;

        StackNode(T data){
            this.data = data;
        }
    }

    private StackNode&lt;T&gt; top = null;
    private int size;

    public MyStack(){}

    public int size(){
        return size;
    }

    T pop(){
        if(top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        size--;
        return item;
    }

    void push(T data){
        StackNode&lt;T&gt; node = new StackNode&lt;T&gt;(data);
        if(top != null){
            node.next = top;
        }
        top = node;
        size++;
    }

    T peek(){
        if(top == null) throw new EmptyStackException();
        return top.data;

    }

    boolean isEmpty(){
        return size == 0;

    }

    void sortStack(){
        MyStack&lt;T&gt; tempStack = new MyStack&lt;T&gt;();

        while(!isEmpty()){
            tempStack.insertToSortedStack(this, pop());
        }

        while(!tempStack.isEmpty()){
            push(tempStack.pop());
        }
    }

    void insertToSortedStack(MyStack&lt;T&gt; auxStack, T item){
        int countPops = 0;
        while(!isEmpty() &amp;&amp; item.compareTo(peek()) &lt; 0){
            auxStack.push(pop());
            countPops++;
        }
        push(item);

        for(int i = 0; i &lt; countPops; i++){
            push(auxStack.pop());
        }

    }

    void printStack(){
        StackNode&lt;T&gt; current = top;
        ArrayList&lt;String&gt; stackAsString = new ArrayList&lt;String&gt;();
        while(current != null){
            stackAsString.add(current.data.toString());
            current = current.next;
        }
        System.out.println("Top -&gt; " + String.join(", ", stackAsString));
    }


}


I ran the code as follows to test that the sorting works as expected.

Main.java

package problem_2_8;

public class Main {

    public static void main(String[] args) {        
        MyStack&lt;Integer&gt; myStack = new MyStack&lt;Integer&gt;();
        myStack.push(5);
        myStack.push(7);
        myStack.push(11);
        myStack.push(5);
        System.out.println("Stack before sorting: ");
        myStack.printStack();
        myStack.sortStack();
        System.out.println("Stack after sorting: ");
        myStack.printStack();

        MyStack&lt;String&gt; myStackOfStrings = new MyStack&lt;String&gt;();
        myStackOfStrings.push("x");
        myStackOfStrings.push("c");
        myStackOfStrings.push("y");
        myStackOfStrings.printStack();
        myStackOfStrings.sortStack();
        myStackOfStrings.printStack();
    }
}
The first thing you should do is assess the visibility of your methods.  Some should be public, and others private.  I don't see any that should stay package-protected as you have them now.

Next, instead of having a printStack() method, you should consider overriding the toString() method.  Just a Java standard.

Now, I don't know if you're as far as multi-threading in your modules, but I can see some cases where your Stack is not thread-safe (particularly around the sorting).  I'll leave the problem of how to solve this as an exercise to the questioner.