は、どのように私は最近、このインタビューの質問をした

Question

スタック（高パフォーマンス）の最初の5つの項目を取得します

どのようにスタック内の最初の5つの項目を取得するには？

スタックあなたが知っているようには

インタビュアーはわずか2操作とスタックのための高性能なアルゴリズム/擬似コードを求め、ポップ（）とプッシュインファーストアウトラストです（）。

私の些細な答えは：

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

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

彼は、我々はより高い性能を持つ別の解決策を持っていますが、私は1つを見つけることができないことを教えてくれました。

Answer 1

は、通信の問題だったようです。スタックに置かれた最初の5つの要素を取得するには、私はどうなる次

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は、逆の順序でスタックS1から最初の5つの要素（Iボトム5つの要素としてこれらを考える）を含みます。

Answer 2

プッシュ（）およびポップ（）の場合は、あなたは、配列内の最後の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

は、元のスタックにサイズ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-stackに格納されます。

Answer 4

はたぶん質問はポップ（遅い信頼性の低いネットワークまたは任意のあなたが考えることができるオーバーRPC）を呼び出すの大きな一定のオーバーヘッドを仮定しました。この場合、次のようになります。

• 読み込み/書き込みポインタを持つ配列としてスタックを実装します。
• パラメータでポップを定義します。ポップ（int型の深さ）。 Pop（5）を呼び出すと、ポインタが5桁だけ前進し、5つの配列エントリのチャンクが一度に呼び出されます。