Streams meet queues

Going back to our functional FIFO queue implementation, do you remember we had to pay the price of occasional reversal? The invariant asserted that the out list would never be empty when the in list is non-empty.

In case the invariant is violated, we can restore it by reversing the in list and turning it into a new out list. We could exploit this laziness to address the once in a while (and possibly costly) reversal. The idea is to make the out list a Stream. The in list remains a strict list, as before. This helps us do the reversal on demand:

    case class LazyQueue(out: Stream[Int], outLen: Int, in: List[Int], inLen: Int) { 
 
    def push(elem: Int) = { 
      val p = makeLazyQueue(out, outLen, elem :: in, inLen + 1) 
      println(s"pushed: ${elem} - ${p}") 
      p 
    } 
 
    def pop: (Int, LazyQueue) = { 
      val q = (out.head, makeLazyQueue(out.tail, outLen - 1, in, inLen)) 
      println(s"popped: ${q._1} and ${q._2}") 
      q 
    } 
 
    def empty = out...