递归搜索堆栈,但保持堆栈不变

Question

我一直在尝试编写一个搜索堆栈的递归函数,但是将堆栈保留在原始状态.我可能会推送并弹出堆栈,但不使用帮助堆栈或任何其他数据结构.

是的,这是家庭作业,所以我不期望完整的编码答案:).关于如何接近堆栈的一点帮助,以便在递归搜索完成后堆栈完好无损将会受到赞赏.

下面给出了在堆栈中搜索指定项目(但是会破坏堆栈)的递归函数:

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()编辑值,递归调用的结果,并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时,你意识到它们是!所以你回来了.
当从递归回来时,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;
   }
}