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 个元素)。

关于algorithm - 如何检索堆栈中的前 5 个项目(更高性能)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8672894/