在堆栈中间找到元素

Question

我在接受采访时被问到这个问题.问题是我会得到一个堆栈,必须在堆栈的中间位置找到元素."top"索引不可用(这样你就不会pop()top/2次并返回答案).假设当pop()返回-1时你将到达堆栈的底部.不要使用任何其他数据结构.

例如:

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

答案:1(我的意思不是中位数.找到中间位置的元素)

递归是唯一的方法吗？

谢谢,

PSY

Answer 1

穿过堆栈,计算深度,并在返回途中返回相应的元素.

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

注意:是的,递归是唯一的方法.不知道堆栈的深度意味着您必须将这些值存储在某处.

Answer 2

递归绝不是唯一的方法;)

但是,递归为您提供了隐含的附加堆栈(即函数参数和局部变量),并且看起来您需要一些额外的存储来存储遍历的元素,在这种情况下,似乎递归可能是给定该约束的唯一方法.