Implement a Queue with two stacks

The idea is like this, when you are adding an element to the queue, you add it to the stack. When removing, since you are supposed to remove the element from the bottom of the stack, so you have to push all the element in the stack to another stack, then remove the one on the top. After that we push all the elements back to our first stack so that the elements stay the same on our next push.

As we can see, if we are doing two continuous pop, we are moving elements needlessly. So we can implement a lazy approch, move the element when we have next push.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s