O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required