Sort stack using two stacks

Question

My program is supposed to sort a stack such that the smallest item are on the top. I can use a temporary stack, but you may not copy the elements into any other data structure. The program works overall, but I was wondering if there is anything that I can do to make it more efficient/better.

import java.util.Stack;
public class SortStack {
 Stack sorted;
 public Stack sort(Stack unsorted) {
 int temp2 = 0; // to keep track of number of top of the sorted stack
 while(!unsorted.isEmpty()) {
 int temp1 = (int) unsorted.pop();
 if(sorted == null) { // if sorted stack is empty, create it and push the first number onto it
 sorted = new Stack();
 sorted.push(temp1);
 System.out.println(temp1 + " pushed from s1 to s2");
 } else if(temp1 >= temp2) { // push onto sorted stack if what is popped from original stack >= unsorted stack 
 sorted.push(temp1);
 temp2 = temp1;
 System.out.println(temp1 + " pushed from s1 to s2");
 } else { // keep on popping from sorted stack to unsorted stack until unsortedTop < sortedTop
 // this will make sure whatever is popped from original stack will not be less than the peek of the sorted stack
 while(temp1 < temp2) {
 int sortedPop = (int) sorted.pop();
 unsorted.push(sortedPop);
 System.out.println(sortedPop + " pushed from s2 to s1");
 temp2 = (int) sorted.peek();
 }
 sorted.push(temp1); // after both stacks are balanced, push element to sorted stack 
 System.out.println(temp1 + " pushed from s1 to s2");
 }
 }
 return sorted;
 }
 public static void main(String[] args) {
 SortStack ss = new SortStack();
 Stack unsorted = new Stack();
 unsorted.push(7);
 unsorted.push(10);
 unsorted.push(5);
 unsorted.push(12);
 unsorted.push(8);
 unsorted.push(3);
 unsorted.push(1);
 ss.sort(unsorted);
 }
}

• rcgldr: This can be done using just one temp variable. Look at sortstacka() in this example. Although the title of the section is sort using 3 stacks, sortstacka() uses just two stacks, the original stack C, and a temp stack B.

Answer 1

Generic type declaration

Your Stacks are missing the type parameter, i.e. in your case Stack<Integer>. This ensures they can only contain Integer objects.

static vs instance fields

sorted is the only instance field used in the only method of your SortStack class. This means it is likely better to exist as a method variable, and in turn your SortStack class becomes an utility class where sort(Stack<Integer> input) is now a static utility method.

Primitive unboxing

On a related note to the first point, you are implicitly relying on primitive unboxing, i.e. converting an Integer to int when you do this:

int temp1 = (int) unsorted.pop();

If a null is lurking in your unsorted object, this will fail.

Debugging and variable naming

If possible, use a logging framework like SLF4J so that you can configure when you want to see the debug statements, instead of simply printing via System.out.println(). Also:

" pushed from s1 to s2"

Isn't that meaningful - is s1 or s2 the sorted one? You may want to specify that. Same goes for temp1 and temp2, it's not possible to identify which contains the previous/current iterative element from the unsorted or sorted stack.

Future considerations

If you don't want to restrict to sorting Stack<Integer> objects, you can generic-fy it as such:

public static <T> sort(Stack<T> input) {
 // ...
}

However, you can't use your arithmetic-based comparison, so you can change that to:

public static <T extends Comparable<T>> sort(Stack<T> input) {
 // ...
 if (fromUnsorted.compareTo(fromSorted) >= 0) {
 // ...
 }
 // ...
}

And if you will like to make it even more 'generic' and cater for non-Comparable types, you can specify a Comparator<T> to do so:

public static <T> sort(Stack<T> input, Comparator<T> comparator) {
 // ...
 if (comparator.compare(fromUnsorted, fromSorted) >= 0) {
 // ...
 }
 // ...
}