c++ - 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

您的解决方案非常好。只需要保存顶部元素(您要弹出)并在递归后恢复它。

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”属性，因为您实际上需要避免显式分配的“内存堆栈”。

Live example here