Найти элемент в середине стека

Мне задали этот вопрос в интервью. Проблема заключалась в том, что мне будет предоставлен стек и нужно будет найти элемент в средней позиции стека. Индекс "top" недоступен (так что вы не поп() сверху /2 раза и ответьте). Предположим, что вы достигнете нижней части стека, когда pop() вернет -1. Не используйте дополнительную структуру данных.

Например:

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

Ответ: 1 (я не имел в виду медианную. Обратите внимание на элемент в средней позиции)

Рекурсия - единственный способ?

Спасибо,

пси

Ответ 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);

Примечание: да, рекурсия - единственный способ. Не зная глубину стека, вы должны где-то хранить эти значения.

Ответ 2

Рекурсия никогда не является единственным способом;)

Однако рекурсия дает вам подразумеваемый дополнительный стек (то есть параметры функции и локальные переменные), и кажется, что вам нужно некоторое дополнительное хранилище для хранения пройденных элементов, в этом случае оказывается, что рекурсия может быть единственным способом это ограничение.

Ответ 3

Вот одно из решений: возьмите два указателя, продвиньте один из них по два шага за раз (быстро), а другой - только по одному шагу (медленно). Если быстрый достигает нижнего, верните медленный указатель, который указывает на средний индекс. Не требуется рекурсия.

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

Ответ 4

Рекурсия кажется единственным способом. Если вы попытаетесь использовать быструю и медленную концепцию указателя во время всплывания, вам нужно будет хранить значения где-то и что нарушает требование дополнительной структуры данных.

Ответ 5

Этот вопрос отмечен c, поэтому для языка программирования c я согласен, что рекурсия - единственный способ. Однако, если поддерживаются первоклассные анонимные функции, вы можете решить их без рекурсии. Некоторые псевдокоды (с использованием синтаксиса лямбда Haskell):

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. f(a) в ветке else используется только для создания новой (!) функции, которая снова называется f.

Предположим, что в стеке есть 3 элемента 10, 20, 30 (снизу вверх), это в основном создает лямбда

(\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))

Ответ 6

"... Не используйте дополнительную структуру данных..."

Тогда задача неразрешима, потому что вам нужно место для хранения всплывающих данных. Вам нужен еще один стек для рекурсии, который также является структурой данных. Не имеет смысла запрещать любую структуру данных и разрешать рекурсию.