Learning Functional Data Structures and Algorithms

Amortized deques

Coming back to deques, we replace the list in the queue with a stream so both in and out become Streams objects. If we try to keep both the streams balanced, we would have an efficient deque implementation.

In this case, by balance, we mean both the streams will have almost the same number of elements. For example, both the streams would be non-empty when the deque contains two or more elements.

Let's say no stream is bigger than the other by a factor, say, c > 1. If one stream becomes too long, we move the elements to the other.

Let's look at stream operations a bit more so we could understand the code that follows:

scala> val s = 1 #:: 2 #:: 3 #:: 4 #:: Stream.empty 
s: scala.collection.immutable.Stream[Int] = Stream(1, ?) 

We define ...