CODEWITHSUNDEEP
c++recursionstack
skepesh
skepesh

Reputation: 15

getNth() item in a stack

I have to implement this function such that it returns the nth item from the stack without using a helper stack (or any other data structure) and still have the stack in its original state in the end, using recursion?

I have managed to implement it but my solution does not leave the stack in its original state.

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

Upvotes: 1

Views: 953

Answers (1)

BiagioF
BiagioF

Reputation: 9715

Your solution is pretty much ok. Just need to save the top element (that you are going to pop) and restore it after recursion.

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

Of course, you will lose the "tail-recursion" property, because you actually need the "memory stack" avoiding to explicitly allocate one.

Live example here

Upvotes: 1

Related Questions