Jeffrey Dilley Jeffrey Dilley - 1 month ago 11
Java Question

Stop peeking at empty stack

I'm checking that a stack is sorted by popping it and comparing the pop to the peek. If the pop is greater than the peek, we know those two elements are in order. I run this loop as long as the stack isn't empty.

The problem I'm running into is with the final element of the stack. I do my final pop, and but it tries to peek at an empty stack to make sure it's in order. Since there is nothing there, I get a runtime error.

public static boolean isSorted(Stack<Integer> s){
boolean result = true;

while(!s.empty()){
if(s.pop() < s.peek()){
result = false;
}
}

return result;
}


I'm trying to do this exclusively with Stack, so using only push pop and peek. Nothing from an ArrayList. How can I fix this problem, while still checking every element?

I've tried storing pop in a temporary variable, but that fixed nothing. Not sure what I was hoping for

Answer

The problem is that you need two items, but empty() checks for just one item. Once you call pop(), you need to do another empty() call prior to executing a peek():

while(!s.empty()){
    // We know we have one element available; store it in "top"
    Integer top = s.pop();
    // If the next element is not available, exit 
    if (s.empty()) {
        break;
    }
    if(top < s.peek()){
        // Once result is set to "false", it never becomes "true"
        // so we might as well return now:
        return false;
    }
}
return true;