Problem with queues

Consider our queue implementation using two lists from the previous chapter. When the out list becomes empty, we substitute it with the reversed in list.

To jog your memory, here is the relevant code snippet:

scala> def pop(queue: Fifo): (Int, Fifo) = { 
     |   queue.out match { 
     |     case Nil => throw new IllegalArgumentException("Empty queue"); 
     |     case x :: Nil => (x, queue.copy(out = queue.in.reverse, Nil)) 
     |     case y :: ys => (y, queue.copy(out = ys)) 
     |   } 
     | } 
pop: (queue: Fifo)(Int, Fifo) 

Note the second case clause where the substitution happens. When we have a large number of insertions, reversing the in list would possibly incur O(n) cost. This would happen once in a while, but that would still be something at least.

So most of our push and pop operations would be O(1), given the occasional in list reversal that could be O(n). This is the concept of amortization, where the occasional cost of reversal is paid off...