элемент getNth () в стеке

Question

Мне нужно реализовать эту функцию таким образом, чтобы она возвращала n-й элемент из стека без использования вспомогательного стека (или любой другой структуры данных) и в конце концов все еще имела стек в своем исходном состоянии, используя рекурсию?

Мне удалось реализовать его, но мое решение не оставляет стек в его первоначальном состоянии.

template <class Type>
Type getNth( stack<Type> & s, int n)
{
    if(n == 1)
    {
        return s.top();
    }
    else
    {   
        s.pop();
        return getNth(s, n - 1);
    }
 }

Answer 1

Ваше решение в значительной степени хорошо.Просто нужно сохранить верхний элемент (который вы собираетесь pop) и восстановить его после рекурсии.

template <typename Type>
Type getNth(std::stack<Type>& s, int n) {
  if (n == 1) {
    return s.top();
  } else {
    auto temp = std::move(s.top());
    s.pop();
    const auto rtn = getNth(s, n - 1);
    s.push(std::move(temp));
    return rtn;
  }
}

Конечно, вы потеряете " tail-recursion "свойство, потому что вам на самом деле нужен «стек памяти», избегающий его явного выделения.

Живой пример здесь