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