Sort a stack in ascending order

Sort a stack in ascending order. You may only use one additional stack to hold items.

Any comments on my solution?
Worst case complexities:
Memory complexity: O(n)
Runtime complexity: O(n^2)

Also, I implemented the Stack class as having Object items and then cast these into Integers to be more general. Is this a good way of doing this?

```
import org.junit.Test;

public class Solution {
// Sort a stack in ascending order
// May only use one additional stack to hold items
// Stack supports push, pop, peek, and isEmpty
private Stack stack;

private Stack auxiliaryStack;

@Test
void testStackIncreasingOrder() {
stack = new Stack();
stack.push(3);
stack.push(2);
stack.push(1);
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}

@Test
void testEmptyStack(){
stack = new Stack();
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}

@Test
void testStackRandomOrder() {
stack = new Stack();
stack.push(3);
stack.push(2);
stack.push(1);
stack.push(5);
stack.push(1);
stack.push(1);
stack.push(12);
stack.push(0);
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}

public static void main(String[] args) {
Solution e = new Solution();
System.out.println("Test reverse sorted stack");
e.testStackIncreasingOrder();
System.out.println("Test empty stack");
e.testEmptyStack();
System.out.println("Test randomly ordered stack");
e.testStackRandomOrder();
}

public void sortStack() {
auxiliaryStack = new Stack();
if (stack.isEmpty()) {
return;
}

while (!stack.isEmpty()) {
Object topOfStack = stack.pop();
if (auxiliaryStack.top != null) {
Object topOfAuxiliary = auxiliaryStack.

Generics

Generics... you want them. In your solution, they would be relatively easy to apply too. Consider your Node class:

class Node {
  Object data;

  Node next;

  public Node(Object item) {
    data = item;
  }

  public Node(Object item, Node n) {
    data = item;
    next = n;
  }
}

Now, that Node only works on Object values, but you want it to be an Integer. Using generics, this is a treat (while we are at it, we will make data and next private and final, and add getters for them...):

class Node {

  private final T data;
  private final Node next;

  public Node(T item) {
    data = item;
  }

  public Node(T item, Node n) {
    data = item;
    next = n;
  }

  public T getData() {
    return data;
  }

  public Node getNext() {
    return next;
  }

}

There, now Node is self contained, immutable, and generic. It can contain any object type, just specify the type you want when you construct it, for example:

Node node = new Node<>(10);

Applying the same logic to your Stack class, we get:

class Stack {
  Node top;

  T pop() {
    if (top != null) {
      T item = top.getData();
      top = top.getNext();
      return item;
    }
    return null;
  }

  void push(T item) {
    Node t = new Node(item, top);
    // commented out, make Node immutable, pass in as constructor
    // t.next = top;
    top = t;
  }

  T peek() {
    return top.getData();
  }

  boolean isEmpty() {
    if (top == null) {
      return true;
    }
    return false;
  }
}

Right, that makes it generic, there are still a bunch of problems... but, it can be easy to use with:

Stack stack = new Stack<>();

With the above stack, you should not need any casts from Object to Integer

Simplifications

Now, looking at some other parts of your code, let's simplify...

Chained constructors: whenever possible, have just one constructor that "does stuff" for your class, and have your other constructors call the main one. Your constructors look like:

public Node(Object item) {
    data = item;
  }

  public Node(Object item, Node n) {
    data = item;
    next = n;
  }

Note that they both access the data = item item directly. It would be better to change your first constructor to be:

public Node(T item) {
      this(item, null);
  }

The above constructor calls the second one with a null value.

Boolean expressions are boolean. If statements test a boolean condition. Why do both?

boolean isEmpty() {
    if (top == null) {
      return true;
    }
    return false;
  }

This is a good one, it can be simply:

boolean isEmpty() {
  return top == null;
}

The push can be simplified too:

void push(T item) {
    Node t = new Node(item, top);
    // commented out, make Node immutable, pass in as constructor
    // t.next = top;
    top = t;
  }

That can be simply:

void push(T item) {
    top = new Node(item, top);
  }

Note that there is no need for the one-argument constructor now in the Node class.

Code duplication is always a red flag. Consider the following methods:

public void printStack() {
    Node current = stack.top;
    while (current != null) {
      System.out.println(current.data);
      current = current.next;
    }
  }

  public void printAuxiliaryStack() {
    Node current = auxiliaryStack.top;
    while (current != null) {
      System.out.println(current.data);
      current = current.next;
    }
  }

Why have the method twice, when instead you can have just:

public void printStack(Node current) {
    while (current != null) {
      System.out.println(current.getData());
      current = current.getNext();
    }
  }

Now, you can call that method with either the stack or the auxilliaryStack top nodes... but, that method really belongs on the stack itself, not outside the stack. Move it to the stack, and it becomes:

public void printStack() {
    Node current = top;
    while (current != null) {
      System.out.println(current.getData());
      current = current.getNext();
    }
  }

Now you can simply do:

stack.printStack();
auxilliaryStack.printStack();

Bugs

The following is a bug:

Object peek() {
    return top.data;
  }

What if the stack is empty? You will get a NullPointerException!

Instead, do:

T peek() {
      return top == null ? null : top.getData();
  }

Sorting

Your algorithm looks sane, but the interface is ... cumbersome. You have a stack, and auxilliaryStack declared as members of the Solution class. Now, the rules of object orientation indicate that the data should be encapsulated. There are two logical ways to implement the sort that I can see. The one is to have a static method that takes a Stack as input, and sorts it in place (creating a temporary, and method-private auxStack to sort with). The other solution adds the sort method to the Stack class itself (and also has an internal auxStack). The second route is the better

StackExchange Code Review Q#84751, answer score: 6