How to get the first 5 items on the stack (higher performance)

Question

Recently I was asked this question:

How to get the first 5 items on the stack?

The stack that you know Last In First Out

The interviewer asked for a high-performance algorithm / pseudo-code for the stack with only two operations: Pop () and Push ().

My trivial answer is:

Stack S2; foreach (item in stack S1) { object item = S1.Pop(); S2.push(item) } for (int i=0 ; i<5 ; i++) Printf(S2.Pop()); 

He told me that we have another solution with higher performance, but I can not find it.

Answer 1

This seems to be a communication problem. To get the first five items that were pushed onto the stack, I would do the following:

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

Final result:

• S1 does not change.
• S2 is empty.
• S3 contains the first five elements (I think it's like the bottom 5 elements) from the S1 stack in the reverse order.

Answer 2

If Push () and Pop () are considered expensive, you can save 5 of them by storing the last 5 elements in an array. If the rest of the stack can be dropped, you can save a lot more.

 #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 

The stack is in the source table, the result is in the cache.

Answer 3

reserve a new auxiliary stack of size 5 for the original stack and save the bottom 5 objects in the auxiliary stack when you press and enter an object to / from the original stack.

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

the bottom 5 elements are stored in the asisst stack.

Answer 4

Perhaps the question involved the large fixed costs of calling Pop (RPC over a slow, untrusted network or whatever you think). In this case, you could:

• Implement the stack as an array with a read / write pointer.
• Define Pop with the parameter: Pop (int depth). Calling Pop (5) will advance the pointer to 5 positions and at the same time output a piece of 5 array entries.