algorithm – 如何检索堆栈中的前5个项目(更高性能)

我最近被问到这个面试问题：

如何检索堆栈中的前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());

他告诉我,我们有另一个性能更高的解决方案,但我找不到一个.

似乎是一个沟通问题.要获得放入堆栈的前五个元素,我将执行以下操作：

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

最终结果：

> S1没有变化.> S2是空的.> S3包含来自堆栈S1的前五个元素(我认为这些是底部的5个元素).