138. Explain the amortised cost of a queue built from two stacks, and why a stack built from queues does not get the same benefit.
MediumQueues
Technical
Show model answer
Track each element's life: one push onto the input stack, at most one pop from it and one push onto the output stack during a transfer, and one final pop. That is at most four stack operations per element, so any sequence of n queue operations costs O(n) in total and each is O(1) amortised, even though one dequeue can take O(n). The accounting (or potential) argument charges the future transfer cost to the enqueue.
When building a stack from queues, the element needed next (the newest) is at the back, and reaching it requires cycling the whole queue every time; no work is saved for later operations. So either push or pop is genuinely O(n) per call, not just in rare cases.