3
\$\begingroup\$

Here's my implementation of sorting a stack in ascending order. The problem statement is as follows :

Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

My Algorithm : Take two stacks I'll call it myStack and helperStack.

  1. If helper stack is empty, simply pop from myStack and push it to helperStack.
  2. If top of helperStack is less than the top of myStack, then pop it from myStack and push it to helperStack. Recurse on two Stacks.
  3. If top of helperStack is less greater than the top of myStack then, recursively pop from helperStack and push it to myStack until the condition is violated. Finally push it to the right position.
  4. End if myStack isEmpty.

Code

static class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

static class Stack{
    Node top;
    String name;
    Stack nextStack;

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

    Stack(String name){
        this.name = name;
    }


    public int pushTo(Stack anotherStack){
        int popped = this.pop();
        anotherStack.push(popped);
        return popped;
    }


    public void _push(int data){
        System.out.println("Pushing : " + data + " to " + this.name);
        if(top==null){
            top = new Node(data);
        }else{
            Node temp = new Node(data);
            temp.next = top;
            top = temp;
        }

    }

    public void push(int... data){
        for(int i : data){
            this._push(i);
        }
    }

    public int pop(){
        if(top==null){
            System.out.println("Error : Stack is empty!!");
            return -1;
        }
        System.out.println("Popping " + top.data + " from " + this.name);
        Node toRet = top;
        top = top.next;
        return toRet.data;
    }   

    public int peek(){
        return top.data;
    }

    public void printStack(){
        Node temp = top;
        while(temp.next!=null){
            System.out.print(temp.data + "->");
            temp = temp.next;
        }
        System.out.println(temp.data);
    }

}//End of Class Stack


public static void sortStack(Stack myStack, Stack helperStack, int curr){
    if(myStack.isEmpty()){
        return;
    }
    if(curr==-1)
        curr = myStack.pop();
    if(helperStack.isEmpty() || curr > helperStack.peek()){
        helperStack.push(curr);
        sortStack(myStack, helperStack, -1);
    }else{
        helperStack.pushTo(myStack);
        sortStack(myStack, helperStack, curr);
    }
}

public static void main(String[] args) {
    Stack someStack = new Stack("someStack");
    Stack helperStack = new Stack("helperStack");
    someStack.push(1,2,3, 200, 4, 22);
    someStack.printStack();
    sortStack(someStack, helperStack, -1);
    helperStack.printStack();
}

Analysis

In worst case , the number of steps executed : n (for popping it out from helperStack) + 1 (pushing the current element at right place) + n (for popping elements out from myStack). So, T(n) = 2n + 1

Solving this recurrence, I get a complexity of \$\theta\$(\$2^n\$) Hence, the algorithm runs in exponential time. Is there any way I could make it faster without violating the condition?

Feel free to suggest and criticize :)

\$\endgroup\$
  • \$\begingroup\$ (3. If top of helperStack is less greater than the top of my looks plusnongood.) Have you already tried to implement some known algorithms for arrays, e.g., bubble sort? Present your findings. \$\endgroup\$ – greybeard Jan 13 '16 at 9:14
1
\$\begingroup\$
public void _push(int data){

You've named a function in a way that suggests it shouldn't be used, but keep it public then support it via push(int... anyway.

There's no need to name your functions something different here; Java can do overloading just fine. If you name your function push, java knows when it needs to call push(int data) or push(int... data).

public int peek(){
    return top.data;
}

Your peek function causes a NullPointerException if the stack is empty. Consider returning -1 as well, since that's the value you use for "there was no data".

\$\endgroup\$
1
\$\begingroup\$

As for a review for your code, I don't see any major issue. I'd just suggest to be consistent with spacing - you sometimes put 2 empty lines between methods and sometimes 1, and also sometimes put an empty line before the end of the method and sometimes don't - and also to be consistent with brackets (put them even in 1 line ifs).

As for the solution, I'd just transform it into an iterative one. Your solution (which is the same one I came with) is similar to the Insertion Sort for arrays, so I'd argue also about the complexity you came up with.

Let's discuss about the algorithm here. We have the following statuses in different times:

  • Start: helperStack contains all the elements while originalStack is empty. The items are supposed to have been transfered from originalStack to helperStack before the algorithm starts.
  • Middle: helperStack contains \$k\$ of the original \$n\$ elements while originalStack contains the rest - \$n - k\$ - of the original elements in an ordered fashion (the greatest of the elements contained in the stack stays on top of it).
  • End: helperStack is empty while originalStack contains all the elements in an ordered fashion (the greatest of the elements contained in the stack stays on top of it).

The steps of the algorithm are the following:

  1. Pick the element on top of helperStack.
  2. If this element is greater than or equal to the element on top of originalStack, or if originalStack is empty, push this element in originalStack.
  3. If this element is smaller than the element on top of originalStack then pop the element on top of originalStack and push it in helperStack, then go to step 2.
  4. If helperStack contains any element go to step 1.

Translated to pseudo-code, it would be something like the following:

void sort(Stack original){
    // swap the content in O(1) time
    Stack helper = original;
    original = new Stack();

    sort(original, helper);
}

void sort(Stack original, Stack helper){
    int tempItem;

    while(!helper.isEmpty()){
        tempItem = helper.pop();

        while(!original.isEmpty() && tempItem < original.peek()){
            helper.push(original.pop());
        }

        original.push(tempItem);
    }
}

Regarding the complexity, like in Insertion Sort, the worst case scenario is when helperStack is sorted. Keep in mind that if you swap the items from stack a to stack b using b.push(a.pop()) the order of the items in b will be the exact opposite of the order in which the same items had in a. This scenario has a complexity of \$O(n^2)\$.

Let me know if anything is unclear.

\$\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.