How would you implement a FIFO queue using only two stacks, and what's the cost?

Keep two stacks, call them in and out. Enqueue: push onto in, O(1). Dequeue: if out is empty, pop every element off in and push each onto out, this reverses the order, so the oldest element (bottom of in) ends up on top of out; then pop out. If out is non-empty, just pop out directly. Because each element is moved from in to out at most once over its lifetime, any single dequeue can be O(n) in the worst case (when it triggers a transfer) but the amortized cost per operation is O(1): the expensive transfer is paid for by the n cheap enqueues that preceded it. This is the standard interview demonstration that a LIFO discipline can be composed into a FIFO one, and it's a clean example of amortized analysis, you can't judge the transfer step in isolation, you amortize it over the operations that made it necessary. (The dual, a stack from two queues, also exists but is less efficient.) In real firmware you'd still just use a ring buffer; this is about proving you understand the access disciplines and amortized cost, not a production recommendation.