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
}