Implement a queue using two stacks

Implementing a queue using two stacks is a typical question for coding interviews. It is a bit artificial, at least I haven't come across any real need, but hey, maybe you need to implement a queue in FORTH. Apart from that it is a nice puzzle ;)

The key insight is that a stack reverses order (while a queue doesn't). A sequence of elements pushed on a stack comes back in reversed order when popped. Consequently, two stacks chained together will return elements in the same order, since reversed order reversed again is original order.

How to do it? We use an in-stack that we fill when an element is enqueued and the dequeue operation takes elements from an out-stack. If the out-stack is empty we pop all elements from the in-stack and push them onto the out-stack. Here is the implementation in Python:

  
class Queue(object):
    def __init__(self):
        self.instack = []
        self.outstack = []
    
    def enqueue(self,element):
        self.instack.append(element)
   
    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()    

Let's try it:

  
q = Queue()
for i in xrange(5):
    q.enqueue(i)
for i in xrange(5):
    print q.dequeue()

0 1 2 3 4

The complexity is amortized O(1) for enqueue and dequeue.