以递归方式搜索堆栈，但将堆栈保持原样

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; 
    } 
}