How do you implement a queue using two stacks?
You use two stacks. One is called the inbox and one is called the outbox. You push everything into the inbox, and when you want to take something out you move everything from the inbox into the outbox, and then you take from the top of the outbox.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, value):
self.inbox.append(value)
def pop(self):
self.move()
if not self.outbox:
return None
return self.outbox.pop()
def peek(self):
self.move()
if not self.outbox:
return None
return self.outbox[-1]
def move(self):
# Only move when the outbox is empty, or the order would be wrong.
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
So how does it work? A queue is first in, first out. A stack is last in, first out. So you cannot use one stack, because the order comes out backwards. But with two stacks you can turn the order round when you need it.
And the key rule is in the move method. You only move from the inbox to the outbox when the outbox is empty. If you moved while the outbox still had things in it, then the items in the inbox would end up on top of the items in the outbox, and the order would be wrong.
push 1, push 2, push 3
the inbox [1, 2, 3]
the outbox []
pop
everything moves over, so the outbox is [3, 2, 1]
and the top of the outbox is 1, which is the oldest item
And what does the interviewer expect? Usually the amortised cost. Each item is pushed once, moved across once, and popped once. So every item is touched a fixed number of times, and the average cost of each operation is constant.
the operation the cost
-------------------- --------------------------------
push O(1) every time
pop O(1) most of the time
pop O(n) in the worst case, when the outbox is empty
the average for pop O(1)
And that is the point of the two stacks. The worst case for a single pop is O of n, but that cost is paid once for all the items that were moved, so you can spread it out. This is called an amortised cost.
And there is a detail worth knowing about. If you use the peek method as well then you must call move there too, otherwise the peek would look at the wrong place.
So the rule to remember is this. Only move when the outbox is empty, and then every item is moved exactly once.
The last question in this topic shows the other direction, building a stack out of queues.