Question

I have the following question:

Write a recursive function to find the Nth element from the top of a stack. For example, if N is 3 the function should return the third element in the stack. Use the following header:

template <class Type> Type getNth( stack<Type> & s, int n)
Although your function may push and pop values from the stack, it must eventually leave the stack in its original state. Your function may NOT use a help stack or any other data structure. You can assume n is a positive integer and that the stack contains at least n elements.

1) I'd like to know what is meant by a "help stack", please and how should I avoid using it?

2) Also, if I used while and for loops would that fine or is that considered a data structure?

If you could assist me in writing this code too, it will be appreciated

Answer 1

1. By help stack , it means that we cannot use any other stack object for finding the nth element except the stack object received by the function

2. No while and for loops are not considered as data structure. These are looping statements. But in recursion we do not use loops. The work of loops is achieved by using recursion

// C++ recursive function to find the Nth element from the top of a stack.

// Assuming stack has a method Pop() that removes and returns the top element of the stack
// Assuming stack has a method Push() that inserts the element at top of the stack
template <class Type>
Type getNth(stack<Type> & s, int n)
{
   // if we have not reached the nth element
   if(n > 1)
   {
       T top = s.Pop(); // remove and get the current top element of the stack
       T a = getNth(s,n-1); // call the getNth with parameters s and n-1
       s.Push(top); // push the current top back to stack
       return a; // return the element returned by getNth
   }
   else // if we have reached the nth element
   {
       T top = s.Pop(); // remove and get the top element of the stack
       s.Push(top);// push the top element back to the stack
       return top; // return this top element
   }
}