A queue is implemented with two stacks, where enqueue pushes onto stack S1 and dequeue pops from S2, refilling S2 from S1 only when S2 is empty. What is the amortised cost of each operation?
Correct answer A. O(1)
Explanation
Each element is pushed onto S1 once, moved to S2 once and popped from S2 once, so over any sequence of operations every element costs a constant amount of work. A single dequeue that triggers a transfer can take O(n), but such transfers are rare enough that the average per operation is O(1). That average-over-a-sequence argument is what amortised analysis means.
Answer checked How we write and check questions
Discussion