java - Java 堆栈比较

Question

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

1. 比较两个 Stack 对象
2. 递归执行此操作
3. 完成此操作的方法完成后，堆栈保持原样（即相同的顺序，相同的项目）。

只有push,pop和isEmpty方法Stack可用。

我正在寻找更多的理论帮助而不是编码帮助，但任何见解都会受到赞赏。

Answer 1

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

现在，想想在从方法调用返回之前要做什么，以便让堆栈保持与调用时相同的方式。

- -编辑 - -

工作 Java 代码（源自Markus A.解决方案，但有趣地使用了“finally”和泛型）：

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 2

在伪代码中，您可以执行以下操作：

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 3

对于递归，将其视为两部分总是有帮助的，一个“设置”和一个递归函数。您的设置将创建适当的情况（创建两个堆栈，将它们传入等），然后调用递归方法，当递归方法完成时，报告结果。

在您的情况下，您可能希望此签名用于“递归”方法：

public boolean compareStacks(Stack one, Stack two)

如果该方法弹出并比较堆栈的顶部两个元素，则它可以立即返回 false （说它们不比较）。如果是这样，您现在有两个堆栈，每个堆栈都比以前短。您已经知道如何比较这两个堆栈，对（您刚刚编写了这样做的方法！）。

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

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

Try/finally 有一个可爱的解决方案（没有捕获，从 try 中返回并在 finally 中推回堆栈），这将使代码非常流畅，但没有它也很容易。