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). For example, given the preceding diagram, when we remove the element 9, we get another version of the persistent queue: V1.

The following figure shows the persistence in action; note the indices for both the versions:

Now let's pop out another element: 7. This will make the out list empty. Of course, this will create another version of the out list...