We're moving into an area whose terminology I'm not as familiar with as the underlying concepts, but what I recall, yes, the actual big-o of a -single- operation, if this is implemented strictly and used as a single ended queue, has a worst case bound of O(n), and a best case bound of O(1), and an average case of O(1), and would be described in big-O terms as "amortized O(1), worst case of O(n)"; much like an arraylist (where the general case for adding at the end is O(1), but when it's full, is actually O(n) as we create a new array and copy elements over, but we describe it as having an amortized cost of O(1)).
Or put another way, for n enqueues, rather than thinking of each enqueue taking one operation, think of it taking two, one now, one deferred, for a still constant enqueue time. On a dequeue where the right side is empty, you have n deferred operations 'stored up', that you then use to reverse the list, and then you use one operation to take the head. So while that -particular- operation actually uses up n+1 operations, the amortized time across the entire sequence of operations so far is constant. And so while you may not have real time dequeue performance of a single operation if implemented strictly (that is, in the worst case, where the right list is empty), the act of enqueueing n things, and dequeueing n things, leads to a total time proportional to n, leading to an averaged constant time per operation.
Now, that said, if you treat it as a double ended queue, there is a worst case in the strict implementation that runs in O(n) per operation; that's by inserting onto one end, then alternately pulling off one end, then the other (so that for every dequeue, we have to reverse the remaining list again). But that's extremely degenerate, and is more egregious than describing quicksort as O(n^2) due to its degenerate case of an already sorted list (since that's far more common a use case than inserting always on one end, and perfectly alternating your dequeues).
1. Average and amortized have very different meanings in algorithmic analysis.
2. One mistake - Okasaki's queues in "Simple and Efficient Purely Functional Queues and Deques" are actually constant-time in the worst-case.
3. Okasaki makes a strong case in his book that the kind of analysis that rejects amortization over ephemeral usage when a structure can be used in a persistent setting is not "more egregious than describing quicksort as O(n^2)". Note, for instance, that quicksort is O(n log n) with high probability with good randomness, and O(n log n) in the worst case with median-of-medians. This quadratic queue case may be degenerate, but the degenerate algorithmic complexity attack of turning hash tables into linked lists by manufacturing collisions is well-documented and worth worrying about. I claim the same is true of queues if a persistent interface is exposed to the user.
Or put another way, for n enqueues, rather than thinking of each enqueue taking one operation, think of it taking two, one now, one deferred, for a still constant enqueue time. On a dequeue where the right side is empty, you have n deferred operations 'stored up', that you then use to reverse the list, and then you use one operation to take the head. So while that -particular- operation actually uses up n+1 operations, the amortized time across the entire sequence of operations so far is constant. And so while you may not have real time dequeue performance of a single operation if implemented strictly (that is, in the worst case, where the right list is empty), the act of enqueueing n things, and dequeueing n things, leads to a total time proportional to n, leading to an averaged constant time per operation.
Now, that said, if you treat it as a double ended queue, there is a worst case in the strict implementation that runs in O(n) per operation; that's by inserting onto one end, then alternately pulling off one end, then the other (so that for every dequeue, we have to reverse the remaining list again). But that's extremely degenerate, and is more egregious than describing quicksort as O(n^2) due to its degenerate case of an already sorted list (since that's far more common a use case than inserting always on one end, and perfectly alternating your dequeues).