Поиск в стеке рекурсивно, но оставить стек без изменений

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. Вы можете понять общую идею из этого ..

---

EDIT:
Я решил добавить простой пример того, что происходит, предположим, ваш стек

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

и вы вызываете getNth (s, 3): вот что будет со стеком
после 1-го pop () и getNth (): [условие остановки не было достигнуто, поэтому продолжайте движение]

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

2nd 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:
после обсуждения в комментариях становится ясно, что ФП хотел что-то немного другое, чем то, что описывает исходный вопрос, поэтому дополнительное редактирование:

Ваше решение ищет элемент и возвращает его. Вероятно, вы хотите, чтобы 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;
   }
}