You implement a queue with two stacks: push onto the inbox, and pop from the outbox, refilling it from the inbox when it is empty. What is the cost of each dequeue?

1. A$O(n)$ every time, because elements are moved between stacks
2. BAmortised $O(1)$, worst case $O(n)$
3. C$O(\log n)$, as for a balanced tree
4. D$O(1)$ in the worst case for every operation