Two-Stack Queue Operations
Problem
Build a first-in, first-out queue from two stacks, using only push to the top, pop from the top and a read of the top. Process a list of operations: ["push", x] adds x, ["pop"] removes and reports the oldest value, and ["peek"] reports it without removing it. Return the reported values in order, reporting None when pop or peek finds the queue empty. Each operation should cost O(1) amortized time.
Examples
Input: ops = [["push", 1], ["push", 2], ["peek"], ["pop"],
["push", 3], ["pop"], ["pop"]]
Output: [1, 1, 2, 3]
Why: values leave in the order they arrivedInput: ops = [["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]]
Output: [7, 8]
Why: after 7 leaves, 8 is the oldest value leftInput: ops = [["pop"], ["push", 4], ["peek"]]
Output: [None, 4]
Why: edge case, popping an empty queue reports NoneHints
0 / 3
Pouring one stack into another reverses the order of its values. After pouring a stack of arrivals, which value is on top?
Use one stack for incoming values and a second one to serve pops and peeks. The real question is when to pour from the first into the second.
Pour only when the serving stack is empty, and then move everything across. While the serving stack has values, its top is always the oldest value still in the queue.
Solution
New values go onto an inbox stack. Pops and peeks read from an outbox stack, and only when the outbox is empty is the whole inbox poured into it, which reverses the arrivals so the oldest ends up on top. Pouring into an outbox that still holds values would bury older values under newer ones, so the empty check is what keeps the order right. Each value is pushed twice and popped twice at most, so m operations cost O(m) in total, which is O(1) amortized per operation. Space is O(n) for the stored values.
def run_queue(ops):
inbox, outbox, out = [], [], []
for op in ops:
if op[0] == "push":
inbox.append(op[1])
continue
if not outbox:
while inbox: # reverse once: the oldest ends on top
outbox.append(inbox.pop())
if not outbox:
out.append(None) # the queue is empty
elif op[0] == "pop":
out.append(outbox.pop())
else:
out.append(outbox[-1])
return out
print(run_queue([["push", 1], ["push", 2], ["peek"], ["pop"], ["push", 3], ["pop"], ["pop"]])) # -> [1, 1, 2, 3]
print(run_queue([["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]])) # -> [7, 8]
print(run_queue([["pop"], ["push", 4], ["peek"]])) # -> [None, 4]Stuck on the idea rather than the code? Queue From Two Stacks covers it.