SortedStack implementation in Java

This is a data structure that supports the push(), pop() and isEmpty() operations and returns the least element on every pop(). In a sense, this works like a PriorityQueue, only in \$O(n)\$ runtime against the \$O(log n)\$ runtime of a PriorityQueue.

My implementation:

public class SortedStack> {

    private int size;
    private  Stack s1;
    private Stack s2;

    public SortedStack(){

        s1 = new Stack<>();
        s2 = new Stack<>();
        size = 0;
    }
    public int compareTo(T other){
        return compareTo(other);
    }
    public void push(T item){

        size++;
        if(s1.getHead() == null){
            s1.push(item);
            return;
        }

        while(!s1.isEmpty()){
            if(s1.peek().compareTo(item)  0) || (s1.peek().compareTo(item) == 0)){
                s1.push(item);
                break;
            }
        }
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }

    }

    public T pop(){
        size--;
        return s1.pop();

    }

    public boolean isEmpty(){
        return size == 0;
    }

}

The Stack implementation that it uses is as follows:

```
public class Stack{
private Node head;

private class Node{
private T data;
private Node next;

public Node(T data){
this.data = data;
next = null;
}
}
public Node getHead(){
return head;
}

public void push(T item){
Node p = new Node((Comparable) item);
if(head == null){
head = p;
return;
}
p.next = head;
head = p;

}
public T pop(){
if(head == null){
System.out.println("Popping off an empty stack!!!");
System.exit(-1);
}
T item = (T) head.data;
head = head.next;
return item;

}

public T peek(){
if(head == null){
System.out.println("Empty Stack!!");
Syst

First up, let's both simplify your low level Stack class, and correct the Generics at the same time.

Stack

The issues with the generics are "obvious" by the numerous times you cast values that should be generically correct anyway.

You also have overly complicated logic in your push method:

public void push(T item){
    Node p = new Node((Comparable) item);
    if(head == null){
        head = p;
        return;
    }
    p.next = head;
    head = p;

}

That can be simply (note, this requires a change to Node that I describe in a moment):

public void push(T item){
    head = new Node(item, head);
}

Right, the change to Node is to add the next to the constructor:

private class Node{
    private final T data;
    private final Node next;

    public Node(T data, Node next){
        this.data = data;
        this.next = next;
    }
}

The System.exit(-1) error handling is also really horrible.... use exceptions!

Finally, why do you have a getHead() method on the Stack? It returns a value that is a private-context Node, so nobody can actually call that method.... right? I am half-surprised that Java lets that compile.

The "final" Stack class could look like:

public class Stack{

    private class Node{
        private final T data;
        private final Node next;

        public Node(T data, Node next){
            this.data = data;
            this.next = next;
        }
    }

    private Node head;

    public void push(T item){
        head = new Node(item, head);
    }

    public T pop(){
        if(head == null){
            throw new IllegalStateException("Cannot pop an empty Stack");
        }

        T item = head.data;
        head = head.next;
        return item;

    }

    public T peek(){
        if(head == null){
            throw new IllegalStateException("Cannot peek an empty Stack");
        }
        return head.data;
    }

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

SortedStack

This class has some simpler problems - naming, and style. It also has some algorithmic problems that may be improved.

s1 and s2 are horrible, horrible names. stack and temp would be better. But, really, there's no reason to have temp at all, you can create it for the duration of the push method only - it does not need to hang around when empty.

You also have the following, very baffling method. This is a "WTF" thing:

public int compareTo(T other){
    return compareTo(other);
}

Please explain that to me? ;-)

Throw it away!

While we are throwing things away, throw out the size as well, it's a distraction, and unnecessary.

Talking about throwing things out..... did you throw out the peek() method when it should actually be there?

One small comment on this code segment:

if((s1.peek().compareTo(item) > 0) || (s1.peek().compareTo(item) == 0)){

How about ( ;-) ):

if(s1.peek().compareTo(item) >= 0) {

Now, ignoring the push(T) method, the rest of the SortedStack class could simply be:

public class SortedStack> {

    private final Stack stack;

    public SortedStack(){
        stack = new Stack<>();
    }

    public T peek() {
        return stack.peek();
    }

    public T pop(){
        return stack.pop();
    }

    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public void push(T item) {
        //TODO - fill this in ;-)
    }

}

Now, abut that push method.... how about:

public void push(T item) {
    Stack temp = new Stack<>();

    // stash away all values less than the new item 
    while (!stack.isEmpty() && stack.peek().compareTo(item) < 0) {
        temp.push(stack.pop());
    }

    // keep the item
    stack.push(item);

    // restore all the smaller items.
    while (!temp.isEmpty()) {
        stack.push(temp.peek());
    }
}

StackExchange Code Review Q#115589, answer score: 11