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

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

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