Checking if a Stack is sorted in ascending order

Question

Write a method isSorted that accepts a stack of integers as a parameter and returns true if the elements in the stack occur in ascending (non-decreasing) order from top to bottom, and false otherwise. That is, the smallest element should be on top, growing larger toward the bottom. For example, passing the following stack to your method should cause it to return true:

bottom [20, 20, 17, 11, 8, 8, 3, 2] top

The following stack is not sorted (the 15 is out of place), so passing it to your method should return a result of false:

bottom [18, 12, 15, 6, 1] top

An empty or one-element stack is considered to be sorted. When your method returns, the stack should be in the same state as when it was passed in. In other words, if your method modifies the stack, you must restore it before returning.

Obey the following restrictions in your solution:

• You may use one queue or stack (but not both) as auxiliary storage.
• You may not use other structures (arrays, lists, etc.), but you can have as many simple variables as you like.
• Use the Queue interface and Stack/LinkedList classes discussed in the textbook.
• Use stacks/queues in stack/queue-like ways only. Do not call index-based methods such as get, search, or set (or use a for-each loop or iterator) on a stack/queue. You may call only add, remove, push, pop, peek, isEmpty, and size.
• Your solution should run in O(N) time, where N is the number of elements of the stack.
• You have access to the following two methods and may call them as needed to help you solve the problem:

public static void s2q(Stack s, Queue q) { ... }

public static void q2s(Queue q, Stack s) { ... }

I'm looking for general feedback that will make my future code better. Are there any glaring issues that you can find that make it harder for you to read my code? Is there a better way you can think of to accomplish this task?

public boolean isSorted(Stack<Integer> s) {
    boolean isSorted = true;
    if (s.size() == 1 || s.isEmpty()) {
        return isSorted;
    }

    Queue<Integer> q = new LinkedList<Integer>();
    while(!s.isEmpty()){
        int s1 = s.pop();
        if (!s.isEmpty()) {
            int s2 = s.peek();
            isSorted &= s2 >= s1;
        }
        q.add(s1);
    }

    while (!q.isEmpty()) {
        s.push(q.poll());
    }

    while (!s.isEmpty()) {
        q.offer(s.pop());
    }

    while (!q.isEmpty()) {
        s.push(q.poll());
    }

    return isSorted;
}

Answer 1

Advice 1

if (s.size() == 1 || s.isEmpty()) {
    return isSorted;
}

You can write more succinctly

if (s.size() < 2) {
    return true;
}

Advice 2

boolean isSorted = true;
if (s.size() == 1 || s.isEmpty()) {
    return isSorted;
}

I suggest you write instead:

if (s.size() == 1 || s.isEmpty()) {
    return true;
}
boolean isSorted = true;

This is a micro-optimization.

Advice 3

Making it generic is not hard. You could demand a type parameter E which extends a Comparable<? super E>

Alternative implementation

I had this in mind:

public static <E extends Comparable<? super E>> 
    boolean isSortedV2(Stack<E> stack) {
    if (stack.size() < 2) {
        return true;
    }

    Stack<E> aux = new Stack<>();
    aux.push(stack.pop());

    while (!stack.isEmpty() && stack.peek().compareTo(aux.peek()) >= 0) {
        aux.push(stack.pop());
    }

    boolean sorted = stack.isEmpty();

    // Restore the input stack:
    while (!aux.isEmpty()) {
        stack.push(aux.pop());
    }

    return sorted;
}

Answer 2

You can simplify the last part (getting the original stack back) a bit, if you use another stack, instead of the queue. Then, you can directly read back the elements of the second stack, and put them back in the first stack.

Something like this:

public static boolean isSorted(Stack<Integer> s) {
    boolean isSorted = true;
    if (s.size() == 1 || s.isEmpty()) {
        return isSorted;
    }

    Stack<Integer> auxiliaryStack = new Stack<Integer>();
    while (!s.isEmpty()) {
        int s1 = s.pop();
        if (!s.isEmpty()) {
            int s2 = s.peek();
            isSorted &= s2 >= s1;
        }
        auxiliaryStack.push(s1);
    }

    while (!auxiliaryStack.isEmpty()) {
        s.push(auxiliaryStack.pop());
    }

    return isSorted;
}

As a side note, I would also recommend more descriptive variable names, to make the code more readable. E.g. stack instead of s, currentElement and nextElement instead of s1 and s2.

Answer 3

Another solution is to use recursion and rebuild using the java stack.

public static void main (String[] args) throws java.lang.Exception
{
    System.out.println(String.valueOf(Execute(true)));
    System.out.println(String.valueOf(Execute(true, 1)));
    System.out.println(String.valueOf(Execute(true, 1, 1)));
    System.out.println(String.valueOf(Execute(true, 20, 20, 17, 11, 8, 8, 3, 2)));
    System.out.println(String.valueOf(Execute(false, 18, 12, 15, 6, 1)));
}

private static boolean Execute(boolean expected, int... values ){

    Stack<Integer> stack = new Stack<Integer>();
    for(int value : values){
    stack.push(value);
    }
    return expected == CheckNotDescending(stack);
}

private static boolean CheckNotDescending(Stack<Integer> stack)
{
    if (stack.size() <= 1) return true;
    int value = stack.pop();
    boolean ret =  stack.isEmpty()
                    || ((value <= stack.peek())
                         && CheckNotDescending(stack));
    stack.push(value);
    return ret;
}

Answer 4

Maybe less elegant but you can achieve that with only one Stack (or any kind of collection) by using the Iterator. If you are using the generics you can also accept more kind of elements.

public static <E extends Comparable<E>> boolean isSorted(Stack<E> stack) {
    return isSorted(stack.iterator());
}

public static <E extends Comparable<E>> boolean isSorted(Iterator<E> it) {
    if ( !it.hasNext() ) {
        return false;
    }
    E head = it.next();
    E next;
    while ( it.hasNext() ) {
        next = it.next();
        if ( head.compareTo(next)<0 ) {
            return false;
        }
        head = next;
    }
    return true;
}