0
\$\begingroup\$

This is my attempted solution to cracking the coding interview exercise 3.5. Looking for any feedback on coding style or the algorithm anywhere I can improve really.

The problem specification is as follows.

Write a program to sort a stack such that the smallest items are on the top. You can use an additional temp stack, but you may not copy the elements into any other data structure (such as an array). The stack supports push, pop, peek and isEmpty.

MyStack.java

package problem_2_8;

import java.util.ArrayList;
import java.util.EmptyStackException;

public class MyStack<T extends Comparable<T>> {

    private static class StackNode<T extends Comparable<T>> {
        T data;
        StackNode<T> next;

        StackNode(T data){
            this.data = data;
        }
    }

    private StackNode<T> top = null;
    private int size;

    public MyStack(){}

    public int size(){
        return size;
    }

    T pop(){
        if(top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        size--;
        return item;
    }

    void push(T data){
        StackNode<T> node = new StackNode<T>(data);
        if(top != null){
            node.next = top;
        }
        top = node;
        size++;
    }

    T peek(){
        if(top == null) throw new EmptyStackException();
        return top.data;

    }

    boolean isEmpty(){
        return size == 0;

    }

    void sortStack(){
        MyStack<T> tempStack = new MyStack<T>();

        while(!isEmpty()){
            tempStack.insertToSortedStack(this, pop());
        }

        while(!tempStack.isEmpty()){
            push(tempStack.pop());
        }
    }

    void insertToSortedStack(MyStack<T> auxStack, T item){
        int countPops = 0;
        while(!isEmpty() && item.compareTo(peek()) < 0){
            auxStack.push(pop());
            countPops++;
        }
        push(item);

        for(int i = 0; i < countPops; i++){
            push(auxStack.pop());
        }

    }

    void printStack(){
        StackNode<T> current = top;
        ArrayList<String> stackAsString = new ArrayList<String>();
        while(current != null){
            stackAsString.add(current.data.toString());
            current = current.next;
        }
        System.out.println("Top -> " + String.join(", ", stackAsString));
    }


}

I ran the code as follows to test that the sorting works as expected.

Main.java

package problem_2_8;

public class Main {

    public static void main(String[] args) {        
        MyStack<Integer> myStack = new MyStack<Integer>();
        myStack.push(5);
        myStack.push(7);
        myStack.push(11);
        myStack.push(5);
        System.out.println("Stack before sorting: ");
        myStack.printStack();
        myStack.sortStack();
        System.out.println("Stack after sorting: ");
        myStack.printStack();

        MyStack<String> myStackOfStrings = new MyStack<String>();
        myStackOfStrings.push("x");
        myStackOfStrings.push("c");
        myStackOfStrings.push("y");
        myStackOfStrings.printStack();
        myStackOfStrings.sortStack();
        myStackOfStrings.printStack();
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I understand the task that you should write a program using an existing stack with the given operations (and a second temp one) to sort the contents of the first, and not implement a stack by yourself. \$\endgroup\$ – P.J.Meisch Oct 9 '16 at 19:02
  • \$\begingroup\$ Thank you for clarifying, I will fix that in a follow up question. \$\endgroup\$ – newToProgramming Oct 10 '16 at 16:59
1
\$\begingroup\$

The first thing you should do is assess the visibility of your methods. Some should be public, and others private. I don't see any that should stay package-protected as you have them now.

Next, instead of having a printStack() method, you should consider overriding the toString() method. Just a Java standard.

Now, I don't know if you're as far as multi-threading in your modules, but I can see some cases where your Stack is not thread-safe (particularly around the sorting). I'll leave the problem of how to solve this as an exercise to the questioner.

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