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:
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)
Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
