以遞歸方式搜索堆棧，但將堆棧保持原樣

Question

我一直在試圖編寫一個遞歸函數來搜索堆棧，但將堆棧保留在原始狀態。我可能會點擊 h並彈出堆棧，但不能使用幫助程序堆棧或任何其他數據結構。

是的，這是家庭作業，所以我不期望一個完整的編碼答案:)。有關如何接近堆棧的一些幫助，以便在遞歸搜索完成後堆棧完好無損將不勝感激。

的遞歸函數，其搜索棧指定的項目（但破壞堆棧中的）標註：

template <class Type> 

Type getNth(stack(Type) & s, int n) 

{ 

    if(s.empty()) 
     return -1; 
    if(s.top() == n) 
     return s.top(); 
    if(s.top() != n && s.empty()) 
     return -1; 
    else 
     s.pop(); 
     return getNth(s, n); 
} 

這工作，到目前爲止。 任何幫助非常感謝

Answer 1

你應該存儲pop() ED值，遞歸調用的結果，並push()的pop() ED值回，才返回。

你別的看起來應該是這樣的：除了那個以外，它看起來精]

else 
    temp = s.pop(); 
    retVal = getNth(s, n); 
    s.push(temp); 
    return retVal; 

（*），原諒我沒有報關temp和retVal，您可以瞭解從這個總體思路..

---

編輯：
我決定增加一個簡單的例子發生了什麼，假設你的堆棧

|1| 
|2| 
|3| 
|4| 
--- 

，你叫getNth（S，3）：這會發生什麼事第一個pop（）方法和getNth（）之後的堆棧
：停止沒有達到條件，所以一直走下去]

|2| 
|3| 
|4| 
--- 

第二pop（）方法，getNth（）：再次，繼續前進]

|3| 
|4| 
--- 

現在

，當你檢查是否s.top（）== N，你知道他們是！所以你回來n。
來從遞歸回來的時候，s.push(temp)被調用，temp==2，所以我們得到：

|2| 
|3| 
|4| 
--- 

，我們從遞歸再次返回retVal的，現在回來了，我們再次使用s.push()，我們得到：

|1| 
|2| 
|3| 
|4| 
--- 

原來的堆棧！並返回遞歸返回的相同returnVal！

注：這不是你的問題，但該功能的名稱所暗示的，你不想回到你正在尋找的價值，而是在堆棧中的第n個元素，這意味着，如果你的籌碼是：

|5| 
|8| 
|8| 
|8| 
|2| 
|4| 
--- 

getNth(2)需要返回8，而不是2，因爲你的問題描述。
但是我不太可能知道，如果是這樣的話，我認爲你有足夠的工具來處理這個問題，沒有太多問題！

祝你好運！

---

編輯2：
在評論中討論後，很明顯的是，OP想要的東西有點不同，那麼原來的問題描述了，等於是額外編輯：

你解決方案是搜索一個元素並返回它，可能你想要做的是COUNT，直到這些元素，然後返回，應該是這樣的[再次，不聲明所有變量，它不會編譯，它只是一個方向] ：

template <class Type> 
Type getNth(stack(Type) & s, int n) 
{ 
    if(s.empty()) {return -1; } //note that in C++ throwing an exception here will be more wise, since -1 might be not matching to Type 
    else if(n == 0) { return s.top(); } 
    else { 
     temp = s.pop(); 
     retVal = getNth(s, n-1); 
     s.push(temp); 
     return retVal; 
    } 
}