We are to account for the total work performed by a sequence of n operations by showing that any sequence of n operations can be executed in cn steps for some constant c . Dividing by n , we obtain the result that each operations takes c steps when amortized over the entire sequence. The key is to observe first that the work required to execute a sequence of queue operations may be apportioned to the elements themselves, then that only a constant amount of work is expended on each element. Arrival requires constant time to add the element to the back of the queue. Transit consists of being moved from the back to the front by a reversal, which takes constant time per element on the back.
Departure takes constant time to pattern match and extract the element.
Thus at worst we require three steps per element to account for the entire effort expended to perform a sequence of queue operations. This argument can be made rigorous as follows. The general idea is to introduce the notion of a charge scheme that provides an upper bound on the actual cost of executing a sequence of operations. An upper bound on the charge will then provide an upper bound on the actual cost. Down to specifics.