Implement a Queue Using Two Stacks

Implement a FIFO queue using only two stacks as the underlying storage (you may only push, pop, peek, and check emptiness on each stack - no other data structure is allowed). You will be given a sequence of operations: "ENQUEUE x" adds the integer x to the back of the queue, and "DEQUEUE" removes and reports the value currently at the front of the queue, or reports that the queue is empty if it has no elements. Process the operations in the order given.

Input: The first line contains the integer Q. Each of the next Q lines is either "ENQUEUE x" or "DEQUEUE". Output: For every DEQUEUE operation, print the value removed from the front of the queue on its own line, or print "EMPTY" if the queue had no elements at that time.

1 <= Q <= 100000 (number of operations), -10^9 <= x <= 10^9

The 'lazy transfer, only when needed' strategy is what turns this from a naive O(n)-per-operation simulation into an O(1)-amortized one - a broadly useful technique whenever repeated work can be deferred until it's genuinely necessary.

Build a FIFO (first-in-first-out) queue using only two stacks (which are naturally LIFO, last-in-first-out). Brute force: Re-transfer elements between the two stacks on EVERY single enqueue (rather than only when 'out' becomes empty) - this works but does far more copying than necessary, since it re-reverses elements that didn't need to move yet. Optimised: Only transferring from 'in' to 'out' when 'out' is EMPTY (a lazy transfer) means each element is moved between stacks at most ONCE across its entire lifetime in the queue - this amortizes the transfer cost, giving O(1) AMORTIZED time per operation even though a single dequeue occasionally costs more.

1. Use one stack purely for INCOMING elements (call it 'in') and a second purely for OUTGOING elements (call it 'out'). 2. On ENQUEUE, just push onto the 'in' stack. 3. On DEQUEUE, if the 'out' stack is empty, pop EVERYTHING from 'in' and push it onto 'out' first (this reverses the order back into correct FIFO order) - then pop and return 'out's top.

Time: O(1) amortized per operation - occasional expensive transfers are offset by many cheap operations, averaging out to constant time. Space: O(n), for the two stacks holding all current queue elements combined.

Consecutive DEQUEUE calls on an empty queue must each print "EMPTY"; with up to 100000 operations, the transfer between stacks must be amortized O(1) per operation, not done on every single call.

Be ready to explain the AMORTIZED analysis clearly - a single dequeue CAN cost O(n) if a full transfer happens, but since each element is only ever transferred once, the cost averages out to O(1) per operation over any sequence of operations.