Implement Queue using Stacks

Build a first-in-first-out queue using only two stacks (only push to top, pop from top, look at top, size/empty). Support:

• push x — add x to the back of the queue
• pop — remove the front element and print it
• peek — print the front element
• empty — print true if the queue is empty, otherwise false

Input:

• line 1: q
• next q lines: one operation each. pop and peek are only used when the queue is not empty.

Output: one line for every pop, peek and empty.

Constraints: 1 ≤ q ≤ 10⁵, −10⁴ ≤ x ≤ 10⁴.

The trick: push onto an in stack. To pop, take from an out stack — and only when out is empty, pour everything from in into out (which reverses the order). Each element moves at most twice, so every operation is amortised O(1).