Skip to interview prep
Apexed

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.

Explain the amortised cost of a queue built from two stacks, and why a stack built from queues does not get the same benefit. — Data structures & algorithms int