A first-in, first-out queue made of two stacks: push onto in, pop off out, and move everything from in to out only when out is empty. One dequeue can cost 2n + 1, but every value moves across once, so any m operations cost at most 3m: O(1) amortized.
This interactive visualization needs JavaScript.