のJavaスタックの比較

Question

私はこれを達成するためにどのように思ったんだけど：

1. は、二つのスタックが
2. 彼らがいたとして、これは再帰的に
3. は、これが完了しないメソッドの後、スタックが残っているかをオブジェクトの比較 で始まります（つまり、同じ注文、同じアイテム）。

のみStackためpush、popとisEmpty方法が可能です。

私は理論的な助けをコーディングヘルプより探していますが、どんな洞察も高く評価されます。

Answer 1

それは常に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 2

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

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

--- EDIT ---

（マルクスA.溶液からの、しかし "ついに" の興味深い使用とし、ジェネリックで得られた）作業Javaコード：

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。あなたの設定は適切な状況を作り出し（2つのスタックを作成し、それらを渡すなど）、再帰的メソッドを呼び出し、再帰的メソッドが完了したら結果を報告します。

あなたはおそらく、「再帰的」方法のために、この署名をしたい、あなたの場合は

：

public boolean compareStacks(Stack one, Stack two) 

その方法は、&は、スタックの最上部牽引要素を比較して表示された場合、それは彼らドンを言って（右クリックfalseを返すことができます比較しない）。そうした場合は、2つのスタックがあり、それぞれが以前よりも短くなっています。あなたはすでに、これらの2つのスタックを比較する方法を知っています。（これを行う方法を書いたばかりです！）

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

比較しない場合にスタックを復元するのはややこしいでしょう。compareStackが失敗すると、現在の "compareStack"が以前の状態に正しく渡されます。成功していますが、それは実装の詳細です。ちょうど私がそれらを言いたいと思ったので、あなたはそれらを見逃しません。

Try/finally（キャッチなし、試し内からの戻り、最終的にはスタックへのプッシュバック）の可愛い解決策があります。コードをきれいにすることができますが、それがなければ簡単です。