在一个栈中查找中间元素

Question

我在面试中遇到了这个问题。问题是我会收到一个堆栈，并且必须找到堆栈中间位置的元素。“top”索引不可用（因此您不能弹出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

- psy

---

@jancha 不是，中位数是具有中间值的元素。 - flight

@kannan，“递归是唯一的方法吗？”你是在暗示你已经知道了一个解决方案吗？ - flight

递归不就相当于使用另一个栈吗？问题说不允许使用额外的数据结构。这是指“不要使用其他类型的数据结构（除了栈）”，还是“不要使用任何其他可以容纳超过O(1)个元素的结构，包括另一个栈”？ - Omri Barel

@quasiverse 我知道一种使用递归的方法来反转栈中元素的解决方案，只使用弹出和推入操作。我可以用它来找到中间元素。 - psy

@goldenmean 我的意思是弹出栈顶的索引/2次...假设栈顶元素在第100个索引处，那么位于第50个索引处的元素就是中间元素... - 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);

注意：是的，递归是唯一的方法。不知道堆栈的深度意味着您必须在某个地方存储这些值。

- Karoly Horvath

---

如果OP澄清允许递归，那么+1。（对于那些不知道的人来说，这不是拼写错误） - flight

没有其他的数据结构，你必须使用递归将这些值存储在某个地方。 - Karoly Horvath

递归是允许的。我同意你的观点。你必须使用递归来存储值。我以为可能会有其他解决方案。 - psy

Answer 2

递归并不是唯一的选择 ;)

然而，递归为您提供了一个隐含的额外堆栈(即函数参数和局部变量)，如果需要存储遍历元素的额外存储空间，那么似乎递归可能是唯一的选择。

- Ofir

Answer 3

"...不使用任何额外的数据结构。..."

如果不使用额外的数据结构，那么这个任务是无法解决的，因为你需要一个地方存储弹出的数据。为了实现递归，需要另一个栈来存储数据，这也是一种数据结构。禁止使用任何数据结构并允许递归是没有意义的。

- Tomas

Answer 4

这个问题被标记为c，所以对于c编程语言，我同意递归是唯一的方法。然而，如果支持第一类匿名函数，你可以在不使用递归的情况下解决它。以下是一些伪代码（使用Haskell的lambda语法）：

n = 0
f = \x -> 0        # constant function that always returns 0

while (not stack_empty) do
    x = pop
    n = n+1
    f = \a -> if (a == n) then x else f(a)

middle = f(n/2)    # middle of stack

# stack is empty, rebuilt it up to middle if required 
for x in (n .. n/2) do push(f(x))

请注意：在 while 循环期间，没有 (递归) 调用 f。else 分支中的 f(a) 只是用于构建一个新(!) 函数，该函数再次被称为 f。

假设堆栈有三个元素 10、20、30（从底部到顶部），这基本上构建了 lambda 表达式。

(\a -> if a==1
       then 30
       else (\b -> if b==2
                   then 20
                   else (\c -> if c==3
                                  then 10
                                  else (\d -> 0)(c)
                        )
                        (b)
            )
            (a)
)

或者更易读一些

f(x) = if x==1 then 30 else (if x==2 then 20 else (if x==3 then 10 else 0)) 

- nimi

Answer 5

这里有一个解决方案：使用两个指针，将其中一个指针每次前进两步（快指针），另一个指针每次前进一步（慢指针）。如果快指针到达底部，则返回指向中间索引的慢指针。不需要递归。

int * slow = stack;
int * fast = stack;
while(1) {
    if(STACK_BOTTOM(fast)) return slow;
    fast--;
    if(STACK_BOTTOM(fast)) return slow;
    slow--;
    fast--;
}

- rumpel

---

你知道堆栈是什么吗？ 假设这个堆栈是以某种方式实现的，并且您可以访问它的内部。 - flight

一个栈是否定义了随机访问操作？如果没有，你将不得不将弹出的所有内容转移到第二个栈中，但问题明确指出不使用其他数据结构。 - Omri Barel

正确，但这仅仅是提供一个想法。如果使用链表实现，代码需要进行调整，但原则仍然适用。 - rumpel

我同意，仅使用push()和pop()操作，这种方法行不通。 - rumpel

@tenfour 这很可能是一个链表的解决方案。 - flight

Answer 6

递归似乎是唯一的方法。如果您尝试在弹出期间使用快慢指针概念，则需要将值存储在某个地方，这违反了不使用额外数据结构的要求。

- Anoop Menon