Medium Lazy Transfer Stacks & Queues
In plain English: Build a first-in-first-out queue using only two last-in-first-out stacks.
Reversing a stack flips LIFO into FIFO — the lazy transfer (only when output is empty) makes this amortized O(1).
Prompt
Implement a FIFO queue using only two stacks.
Try to write it from scratch before scrolling down.
Solution
class Queue:
def __init__(self):
self.sin = []
self.sout = []
def enqueue(self, x):
self.sin.append(x)
def dequeue(self):
if not self.sout:
# lazy transfer: only when needed
while self.sin:
self.sout.append(self.sin.pop())
return self.sout.pop()
# Test: q = Queue(); q.enqueue(1); q.enqueue(2); q.dequeue() == 1