Problem
I am using two more helper stacks to sort. Kindly suggest improvements in terms of space and time.
import java.util.ArrayDeque;
import java.util.Deque;
public class SortStackAscendingOrder {
Deque<Integer> stackhelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();
public Deque<Integer> sortStack(Deque<Integer> mainStack) {
if (mainStack.isEmpty()) {
return null;
}
while (!mainStack.isEmpty()) {
int mainItem = mainStack.pop();
int helperItem1 = -1;
if (!stackhelper1.isEmpty()) {
helperItem1 = stackhelper1.peek();
}
if (mainItem > helperItem1) {
// push all helperItem1 to helperItem2, till it is in ascending
// order
while (!stackhelper1.isEmpty() && mainItem > helperItem1) {
stackHelper2.push(stackhelper1.pop());
helperItem1 = stackhelper1.peek();
}
// push mainItem.
stackhelper1.push(mainItem);
// bring back all the helperItem2
while (!stackHelper2.isEmpty()) {
stackhelper1.push(stackHelper2.pop());
}
} else {
// directly push in stackhelper1
stackhelper1.push(mainItem);
}
}
return stackhelper1;
}
}
Solution
Possible bug:
The following demo will throw a NullPointerException:
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.addLast(2);
stack.addLast(-1);
stack.addLast(-3);
stack.addLast(1);
System.out.println("Original stack: " + stack);
SortStackAscendingOrder sorter = new SortStackAscendingOrder();
Deque<Integer> sortedStack = sorter.sortStack(stack);
System.out.println("Sorted original stack: " + sortedStack);
stack.clear();
stack.addLast(11);
stack.addLast(8);
stack.addLast(9);
stack.addLast(10);
System.out.println("Another stack: " +
sorter.sortStack(stack));
System.out.println("Sorted original stack again: " + sortedStack);
}
Most likely the problem above is due to the fact that you return stackhelper1, which is an essential internal facility in your algorithm.
API design:
First of all, I would consider implementing the stack sort as a static method that does not “leak” any internals. The idea here is that you sort the input stack: just like sorting methods in java.util.Arrays, all are void and modify the input arrays instead of returning a sorted copy.
All in all, I had this in mind:
public static void sortStack(Deque<Integer> mainStack) {
Deque<Integer> stackHelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();
while (!mainStack.isEmpty()) {
int mainItem = mainStack.pop();
int helperItem1 = -1;
if (!stackHelper1.isEmpty()) {
helperItem1 = stackHelper1.peek();
}
if (mainItem > helperItem1) {
while (!stackHelper1.isEmpty() && mainItem > helperItem1) {
stackHelper2.push(stackHelper1.pop());
helperItem1 = stackHelper1.peek();
}
stackHelper1.push(mainItem);
while (!stackHelper2.isEmpty()) {
stackHelper1.push(stackHelper2.pop());
}
} else {
stackHelper1.push(mainItem);
}
}
mainStack.clear();
mainStack.addAll(stackHelper1);
}
You should take more attention to the naming convention of Java :
Deque<Integer> stackhelper1 = new ArrayDeque<>();
Deque<Integer> stackHelper2 = new ArrayDeque<>();
The variable should be named stackHelper1, the H is what was missing. I don’t like numbered variable names. It always let me wonder if it’s a bad design decision or simply bad names. In this case, I think it’s just a bad name, maybe try to really name it after what they are.
// push mainItem.
stackhelper1.push(mainItem);
You really don’t have to state the obvious in a comment. Just by reading the line of code I can easily understand that you’re pushing mainItem`, that’s what the method is called. Almost all your comments are noise in the code. What would have a been a bit more useful is Javadoc to explain what the method is about and maybe expose your “algo”, something like this javadoc.
if (mainStack.isEmpty()) {
return null;
}
I would have really like to have been warned that using your method with an empty collection would return me null. If I passe you an empty collection, I would have expected to have an empty collection in return. Returning null just expose the user of the method to NullPointerExceptions. You should really ask yourself if returning null is a good thing, in a good number of occasion it will complicate things.
The null pointer exception pointed earlier can be avoided if you just do a check stackhelper1.isEmpty()
if(!stackhelper1.isEmpty())
helperItem1 = stackhelper1.peek();
In terms of improving space complexity, there is a way to sort stack using one stack:-
private static Stack<Integer> sortWithOneStack(Stack<Integer> s1) {
Stack<Integer> s2 = new Stack<Integer>();
while(!s1.isEmpty()){
int topEl = s1.pop();
while(!s2.isEmpty() && s2.peek() > topEl){
s1.push(s2.pop());
}
s2.push(topEl);
}
return s2;
}
You just push the element back to the original stack if that is less than the top of the other stack.
In fact, there is a way to do it without using any external stack at all. Here is the code for it.
public static void sort(Stack<Integer> st){
if(st.isEmpty())
return;
int el = st.pop();
sort(st);
putInSortedOrder(st,el);
}
private static void putInSortedOrder(Stack<Integer> st, int el) {
if(st.isEmpty() || st.peek() < el){
st.add(el);
return;
}
int cur = st.pop();
putInSortedOrder(st, el);
st.push(cur);
}
The secret is that this method uses the system stack. All the techniques are using the same logic but using different stacks.