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

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 (я не имел в виду медиану. Найти элемент в среднем положении)

Является ли рекурсия единственным способом?

Спасибо,

пси

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

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

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

Answer 3

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

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

Answer 4

Этот вопрос помечен 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)) 

Answer 5

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

Answer 6

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

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