Java stack comparison

Question

I am wondering how to do this:

• Compare Two Stack Objects
• Do it recursively
• After the method that does this, the Stacks remain as they should have started with (that is, the same order, the same elements).

Only the push , pop and isEmpty methods for Stack .

I am looking for more theoretical help than coding help, but any understanding would be appreciated.

Answer 1

In pseudo code, you can do something like this:

 boolean compareStacks(a, b) { if (a.isEmpty() != b.isEmpty()) return false; // check if one is empty if (a.isEmpty() && b.isEmpty()) return true; // check if both are empty element_a = a.pop(); // grab elements and compare them element_b = b.pop(); if (((element_a==null) && (element_b!=null)) || !element_a.equals(element_b)) { a.push(element_a); // if they are not equal, restore them and return false b.push(element_b); return false; } result = compareStacks(a, b); // compare shortened stacks recursively a.push(element_a); // restore elements b.push(element_b); return result; // return result from recursive call } 

Answer 2

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

Now think about what to do before returning from the method call to leave the stacks the same as they are specified during the call.

--- EDIT ---

Java working code (obtained from Markus A. solution, but with 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); } } 

Answer 3

With recursion, it always helps to think of it as 2 parts, the “Setup” and the recursive function. Your setup will create the correct situation (create two stacks, pass them, etc.), and then call the recursive method, and when the recursive method is executed, report the results.

In your case, you probably want this signature for the "recursive" method:

 public boolean compareStacks(Stack one, Stack two) 

If this method pops up and compares the top elements of the stack tow, it can return false right then (saying that they are not compared). If they do, you now have two stacks, each one shorter than before. You already know how to compare these two stacks, correctly (you just wrote a method for this!).

at the end, you can “Push” your one element back onto each stack to restore its previous state before returning.

There will be little difficulty in restoring the stack when they are not being compared, and ensuring that if compareStack fails you call, it passes it correctly to the previous state, even if the "current" compareStack is successfully completed, but these are implementation details - I just thought that I mention them so you don’t miss them.

There is a good solution with Try / finally (without catching, returning from try and returning back to the stack at the end), which will make the code pretty smooth, but it is quite simple without it.