Java Stack Comparison

Question

I'm wondering how to accomplish this:

1. Compare two Stack objects
2. Do this recursively
3. After the method that does this is complete, the Stacks remain as they were to begin with (i.e. same order, same items).

Only the push, pop and isEmpty methods for Stack is available.

I'm looking more for theoretical help than coding help, but any insight would be appreciated.

Answer 1

Two stacks are identical if their top level elements are identical, and the remaining stacks are identical (namely, the recursive condition).

Now, think what to do just before returning from the method call, in order to leave the stacks the same way they where given at the invocation time.

---EDIT---

The working Java code (derived from Markus A. solution, but with an interesting use of "finally" and with generics):

static <T> boolean compareStacks(Stack<T> a, Stack<T> b) {
    if (a.isEmpty() != b.isEmpty()) return false; 
    if (a.isEmpty() && b.isEmpty()) return true; 
    T element_a = a.pop(); 
    T element_b = b.pop();
    try {
        if (((element_a==null) && (element_b!=null)) || (!element_a.equals(element_b)))
            return false;
        return compareStacks(a, b); 
    } finally { // restore elements
        a.push(element_a); 
        b.push(element_b);
    }
}