Java堆栈比较

Question

我不知道如何做到这一点：

1. 比较两个栈对象
2. 做这个递归
3. 是 这是否是完整的方法后，仍然书库因为他们以 开头（即相同的顺序，相同的项目）。只有

的push，pop和isEmpty方法Stack可用。

我正在寻找更多的理论帮助比编码的帮助，但任何见解，将不胜感激。

Answer 1

在伪代码，你可以做这样的事情：

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

如果两个堆栈的顶层元素相同，并且其余堆栈是相同的（即递归条件），则两个堆栈是相同的。

现在，请考虑在从方法调用返回之前要做什么，以便使用与调用时给定的方式相同的方式保留堆栈。

---编辑---

工作的Java代码（从马库斯A.解推导，但一个有趣的用 “终于”，并与仿制药）：

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

递归它总是有助于把它看作两个部分，“安装程序”和递归乐趣ction。您的设置将创建适当的情况（创建两个堆栈，将它们传入等），然后调用递归方法，并在递归方法完成时报告结果。

你的情况，你可能想这个签名为“递归”的方法：

public boolean compareStacks(Stack one, Stack two) 

如果该方法弹出&比较堆栈的顶部拖元素，它可以返回假的权利，然后（说他们不没有比较）。如果他们这样做，你现在有两个堆栈，每个堆栈比以前更短。你已经知道如何比较这两个堆栈，正确的（你只是写了这样做的方法！）。

最后，您可以将您的一个元素“推回”每个堆栈，以便在返回之前恢复其之前的状态。

在没有比较的情况下恢复堆栈会有一些小技巧，并且确保如果您调用的compareStack失败，它会将其正确地传递到之前的状态，即使“当前”compareStack成功了，但这些都是实现细节 - 只是认为我会提到那些，所以你不会忽略它们。

Try/finally有一个可爱的解决方案（没有捕获，从try中返回并且最终推回栈中），这会使代码非常光滑，但没有它就很容易。