find element in the middle of a stack

Question

I was asked this question in an interview.The problem was i would be given a stack and have to find the element in the middle position of the stack."top" index is not available (so that you don't pop() top/2 times and return the answer).Assume that you will reach the bottom of the stack when pop() returns -1.Don't use any additional data structure.

Eg:

stack   index
----- 
 2    nth element
 3
 99
 .
 1    n/2 th element
 .
 -1   bottom of the stack(0th index)

Answer: 1 (I didn't mean the median.Find the element in middle position)

Is recursion the only way?

Thanks,

psy

Answer 1

Walk through the stack, calculate the depth and on the way back return the appropriate element.

int middle(stack* s, int n, int* depth) {
  if (stack_empty(s)) {
    *depth = n;
    return 0; //return something, doesn't matter..
  }
  int val = stack_pop(s);
  int res = middle(s, n+1, depth);
  stack_push(s, val);
  if (n == *depth/2)
    return val;
  return res;
}

int depth;
middle(&stack, 0, &depth);

Note: yes, recursion is the only way. Not knowing the depth of the stack means you have to store those values somewhere.

Answer 2

Recursion is never the only way ;)

However, recursion provides you with an implied additional stack (i.e. function parameters and local variables), and it does appear that you need some additional storage to store traversed elements, in that case it appears that recursion may be the only way given that constraint.