Как получить первые 5 элементов в стеке (более высокая производительность)

Question

Мне недавно задали этот вопрос:

Как получить первые 5 элементов в стеке?

Стек, как вы знаете, является последним первым полученным

Интервьюер запросил алгоритм / псевдокод с высокой производительностью для стека только с 2 операциями, Pop () и Push ().

Мой тривиальный ответ:

Stack S2;
foreach (item in stack S1)
{
  object item = S1.Pop();
  S2.push(item)
}

for (int i=0 ; i<5 ; i++)
 Printf(S2.Pop());

Он сказал мне, что у нас есть другое решение с более высокой производительностью, но я не могу его найти.

Answer 1

Кажется, была проблема со связью.Чтобы получить первые пять элементов, которые были помещены в стек, я бы сделал следующее:

input: Stack S1;
Stack S2;
Stack S3;
Object[5] elementArray;
int elementIndex = 0;

foreach (item in Stack S1)
{
  elementArray[elementIndex] = item;
  elementIndex = ++elementIndex % 5 // modulus operation.
  S2.push(item); // only needed to restore S1 to its' original state.
}

elementIndex = ++elementIndex % 5 // advance to the 5th element from the bottom.

for (int index = 0; index < 5; ++index)
{
  S3.push(elementArray[elementIndex]);
  elementIndex = ++elementIndex % 5
}

foreach (item in Stack S2)
{
  S1.push(item);
}

Конечный результат:

1. S1 не изменился.
2. S2 пуст.
3. S3 содержит первые пять элементов (я думаю, что они являются нижними 5 элементами) из стека S1 в обратном порядке.

Answer 2

Если Push () и Pop () считаются дорогими, вы можете сохранить 5 каждого, сохранив последние 5 элементов в массиве. Если остальная часть стека может быть сброшена, вы можете сэкономить гораздо больше.

#ifdef NEED_REST_OF_STACK
Stack newstack;
#endif

object[] cache=new object[5];
object tmp;
int i=0;

while (tmp=originalstack.Pop()) {
  cache[i%5]=tmp;
#ifdef NEED_REST_OF_STACK
  if (i>4) newstack.Push(cache[(i-1)%5]); //This assumes a%b>=0 in this language
#endif
  i++;
}

#ifdef REST_OF_STACK_MUST_BE_IN_ORIGINAL_ORDER
  //Revert stack back
  while (tmp=newstack.Pop()) originalstack.Push(tmp);
#else
  originalstack=newstack;
#endif

Стек находится в оригинальной стопке, результат в кэше.

Answer 3

Возможно, этот вопрос предполагал большие постоянные издержки вызова Pop (RPC по медленной ненадежной сети или что-то еще, о чем вы можете подумать). В этом случае вы могли бы:

• Реализация стека в виде массива с указателем чтения / записи.
• Определить Pop с помощью параметра: Pop (int глубина). Вызов Pop (5) продвинет указатель на 5 позиций и принесет блок из 5 элементов массива одновременно.

Answer 4

резервируйте новый вспомогательный стек размером 5 для исходного стека и сохраняйте нижние 5 объектов в вспомогательном стеке при перемещении и извлечении объекта в / из исходного стека.

Stack OriS;
Stack AsiS;     #stack size is 5


#push

if(AsiS.size() <5) AsiS.push(obj);
OriS.push(obj);

#pop

if(OriS.size() <= 5) AsiS.pop();
OriS.pop();

нижние 5 элементов хранятся в asisst-стеке.