Recently I encountered a trivial but interesting question. "How to implement a queue using two stacks ? ". My first reaction was "Why would I do that ..? " But if I am forced to do such a thing, how would I go about doing it ? So, here is how we implement a queue using two stacks.
Logic : We'll implement a FIFO queue using two stacks. Lets call the stacks Instack and Outstack. An element is inserted in the queue by pushing it into the Instack. An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
We start with a Stack Interface :
and a class that implements this interface :
Now we come to actual class that implements a Queue using two stacks.