java - Javaスタックの比較

Question

私はこれをどのように達成するのか疑問に思っています：

1. 2つのStackオブジェクトを比較します
2. これを再帰的に実行します
3. これを行うメソッドが完了した後、スタックは最初の状態のままになります（つまり、同じ順序、同じアイテム）。

push、popおよびのisEmptyメソッドのみStackが使用可能です。

私はコーディングの助けよりも理論的な助けを探していますが、どんな洞察もいただければ幸いです。

Answer 1

最上位の要素が同一である場合、2つのスタックは同一であり、残りのスタックは同一です（つまり、再帰条件）。

ここで、呼び出し時に指定されたのと同じ方法でスタックを残すために、メソッド呼び出しから戻る直前に何をすべきかを考えてください。

- -編集 - -

動作する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

再帰では、それを「セットアップ」と再帰関数の 2 つの部分と考えると常に役立ちます。セットアップは適切な状況を作成し (2 つのスタックを作成し、それらを渡すなど)、再帰メソッドを呼び出し、再帰メソッドが完了すると結果を報告します。

あなたの場合、おそらく「再帰的」メソッドにこの署名が必要です。

public boolean compareStacks(Stack one, Stack two)

そのメソッドがスタックの最上位の 2 つの要素をポップして比較すると、その時点で false が返される可能性があります (それらは比較されないことを示します)。その場合、スタックが 2 つになり、それぞれが以前より短くなります。これら 2 つのスタックを比較する方法は既にご存じでしょう (そのためのメソッドを作成しただけです!)。

最後に、1 つの要素を各スタックに「プッシュ」して、戻る前に以前の状態に戻すことができます。

それらが比較されない場合にスタックを復元することには少し注意が必要です。また、呼び出したcompareStackが失敗した場合、「現在の」compareStackが成功したとしても、それを前の状態に適切に渡すことを保証しますが、実装の詳細です。見落とさないように、それらについて言及したいと思いました。

Try/finally (キャッチなし、try 内から戻り、finally でスタックにプッシュバックする) を使用したかわいいソリューションがあり、コードがかなり滑らかになりますが、それがなくても十分に簡単です。