3
\$\begingroup\$

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;

    }

}
\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Why mainStack.clear()? There is no break in the while loop, so it can only exit naturally when mainStack.isEmpty() is true. There is no need to clear an empty stack. \$\endgroup\$ – 200_success Feb 23 '16 at 18:27
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.