Implement Queue using Stacks

class MyQueue:
    def __init__(self):
        self.in_stack, self.out_stack = [], []
    def push(self, x):
        self.in_stack.append(x)
    def peek(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]
    def pop(self):
        self.peek()
        return self.out_stack.pop()
    def empty(self):
        return not self.in_stack and not self.out_stack

Implement Queue using Stacks. Build a first in, first out queue with push, pop, peek and empty, using only two stacks. A stack can only touch its top.

LeetCode's example: push one, push two. Peek returns one, the oldest. Pop returns one. Empty? No, two is waiting: false.

The naive way keeps the oldest tray on top. Every push moves all the trays to a helper stack, puts the new one at the bottom, and moves them back. The fifth push moves eight trays: order n per push.

The key idea: two stacks, In and Out. Push drops onto In. Pop and peek take from Out. Only when Out is empty, pour all of In onto Out. Pouring flips the order, so the oldest tray lands on top.

In code, push is one append. Peek refills Out only when it's empty, then reads its top. Pop calls peek, then pops Out. Empty checks both.

Push one and two onto In. Peek: Out is empty, so pour two, then one. One is on top: peek gives one, pop serves one. Empty? Out holds two: false. Push three and four. Pop: Out isn't empty, so serve two, no pouring. Pop again: Out is empty, so pour four, then three, and serve three.

Each tray is pushed once, poured once, and popped once. One pour can be long, but earlier pushes pay for it: amortized constant time per operation. The two stacks hold n trays: order n space.

Push onto In, pour when Out runs dry, serve from Out. That's Implement Queue using Stacks.