Learning Functional Data Structures and Algorithms

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 ...