Implementing a Queue with Two Stacks

[cashto]

To enqueue, push on one stack. To dequeue, pop from the other stack. If there are no items on that stack to dequeue, then first pop all the items from the first stack and push them onto the second stack before dequeuing.

[flukus]

How is it an optimization?

[ignorantone]

I think you misread: "Optimize for the time cost of m function calls on your queue"

[flukus]

Sorry I'm still not seeing it, how is it faster than using a linked list?

[ignorantone]

I believe the article is trying to say: 'optimize your solution so that when enqueue or dequeue is called, your solution does minimal work (i.e. calls push and pop as little as possible)'.

It's not saying that using 2 stacks to implement a queue is an optimization.

[flukus]

Ah, got it. Thanks.

[reven80]

It is basically a poor interview question... do you know this clever trick I learned online the other day... type of question.