getNth() item in a stack

Question

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

Recurse, go upto that nth element and push everything back from the call stack. — piepi, Sep 25 '19 at 14:09
A `stack` is the wrong data structure for this. You need to have another data structure to store the elements you `pop` as you dig into it to find the one you want. Use a sequential container with random access like `vector` to avoid this problem. — François Andrieux, Sep 25 '19 at 14:46
`std::stack` technically exposes it's underlying container but it is `protected`. Possible duplicate of [Trying to access an index of an std::stack](https://stackoverflow.com/questions/13428618/trying-to-access-an-index-of-an-stdstack). — François Andrieux, Sep 25 '19 at 14:55

BiagioF · Accepted Answer · 2019-09-25T14:24:53.053

1

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

edited Sep 25 '19 at 14:24

answered Sep 25 '19 at 14:11

BiagioF

9,368
2
26
50

But technically, since you are using the call stack to store popped elements as a "helper stack" it violates the "without using a helper stack" requirement. This answer just makes it less obvious that this requirement is violated by avoiding declaring a `stack` object explicitly. – François Andrieux Sep 25 '19 at 14:44
@FrançoisAndrieux Yeah, more or less what I've written in my last point. You **need** the *memory stack*. The OP's constraint states *"data structure"*, so I assumed "explicit" stack. Also because it is very easily demonstrable, this problem cannot be solved without memory. So the other way around wouldn't make sense. – BiagioF Sep 25 '19 at 14:51
Conceptually, that is true. But in practice, for reasons that nobody has been able to explain to me, the C++ implementation provides access to the underlying container but it's `protected`. See the `c` member for [`std::stack`](https://en.cppreference.com/w/cpp/container/stack). Using this *requires* that you inherit from `std::stack`. So it makes it questionable if this is applicable to a question about `std::stack` in general. Same thing for `std::queue`. – François Andrieux Sep 25 '19 at 14:58
@FrançoisAndrieux I don't completely get your point. Indeed, your "solution" (that is, to hack the data structure) is not general (and pretty dirty, IMHO). My assumption is regarding the proper definition of a stack, as defined in whatever computer science book. Despite the fact, my example snippet is implemented with `std::stack` just for the sake of simplicity. If you access `c` you are actually using a `std::vector`(not a stack data structure) ... – BiagioF Sep 25 '19 at 15:08
The only point I want to make is that, from a practical stand point you *can* solve this with constant memory for certain use cases. The mechanisms are ugly but well defined and provided by the standard for this purpose. Though I don't understand why they chose to provide this, much less why they decided to provide it the way they did. And I *did* start by saying that you are conceptually correct (with regards to the abstract concept of a stack, without regards to the implementation). Given an idiomatic stack, the solution you've shown is probably the best you can get. – François Andrieux Sep 25 '19 at 15:18
@FrançoisAndrieux thanks for explaining me your point again. Like you, I just pretend that part of the standard does not exist ;) – BiagioF Sep 25 '19 at 15:20

getNth() item in a stack

1 Answers1