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中返回並且最終推回棧中），這會使代碼非常光滑，但沒有它就很容易。