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

Functional FIFO queues

We know by now that all this mutating won't work when we deal with persistent data structures (also known as versioned data structures). How can we implement these queues so that when an element is enqueued or dequeued, the earlier version of the data structure would be preserved?

The design is beautiful; it involves two lists. The following diagram shows two lists, namely in and out:

Functional FIFO queues

The out list holds the elements that will be popped out. We just remove the head element and return it. The in list is where new elements are inserted, that is, prepended. As we have already seen, both list prepend and head removal are O(1)

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