AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumstackqueueamortised

~90s

A queue from two stacks

A queue is built from two stacks: enqueue pushes onto stack A, and dequeue pops from stack B, refilling B by emptying A into it whenever B is empty. What is the amortised cost of one dequeue?

Show the answer and the worked solution

Correct answer: A.

O(1)

Worked solution

  1. One dequeue can be expensive: transferring k elements from A to B costs k pops and k pushes.
  2. But an element moves from A to B exactly once, so over its lifetime it is pushed twice and popped twice — a constant amount of work.
  3. Spreading that constant per-element cost across the whole sequence of operations gives an amortised O(1) per dequeue.

Answer: O(1).

The idea

Amortised analysis charges each element for its own total work instead of pricing the worst single operation. The expensive transfer is paid for by the many cheap enqueues that preceded it.

Shortcut. Count total work, not the worst call: no element is pushed or popped more than twice, so any sequence of n operations costs O(n) in all, which is O(1) per operation.

Common trap. O(n) prices the single worst dequeue, the one that empties A into B, instead of averaging over the sequence as amortised cost requires.

Data Structures & Algorithms

5 of 40

Level

Medium

Target time

~90s

PreviousNext
AI InterviewGet started

A queue from two stacks — Aptitude Question

A queue from two stacks: A queue is built from two stacks: enqueue pushes onto stack A, and dequeue pops from stack… Answer and worked solution on CodeKairo.

Question

A queue is built from two stacks: enqueue pushes onto stack A, and dequeue pops from stack B, refilling B by emptying A into it whenever B is empty. What is the amortised cost of one dequeue?

Options

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n log n)
Show the answer and the worked solution

Correct answer: A. O(1)

Worked solution

  1. One dequeue can be expensive: transferring k elements from A to B costs k pops and k pushes.
  2. But an element moves from A to B exactly once, so over its lifetime it is pushed twice and popped twice — a constant amount of work.
  3. Spreading that constant per-element cost across the whole sequence of operations gives an amortised O(1) per dequeue.

Answer: O(1).

The idea

Amortised analysis charges each element for its own total work instead of pricing the worst single operation. The expensive transfer is paid for by the many cheap enqueues that preceded it.

Shortcut. Count total work, not the worst call: no element is pushed or popped more than twice, so any sequence of n operations costs O(n) in all, which is O(1) per operation.

Common trap. O(n) prices the single worst dequeue, the one that empties A into B, instead of averaging over the sequence as amortised cost requires.

All Data Structures & Algorithms questions · placement mock tests