Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Persistent two-list queues: fork FIFO dispatch history

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A persistent two-list queue keeps front and rear chains of immutable linked pairs. New items are consed to the rear, while removal takes the head of the front. When the front empties, reversing the rear yields a new front in FIFO order. Each operation returns a new queue version instead of editing the old one. Existing versions can therefore answer an audit replay after later dispatch actions. The example normalizes eagerly when necessary and returns the removed case ID beside the successor version. It stores IDs, not mutable case records; if record objects changed elsewhere, the queue snapshot would not freeze their contents.

Operational case

A morning queue holds cases 47, 19, and 83. Removing its head returns 47 and a midday version; appending 61 to that version yields an afternoon queue with 19, 83, 61. The morning version still reads 47, 19, 83. Mutating a shared linked node to save an allocation would corrupt both histories. A branch made from an old queue is allowed, but repeated branches can each trigger the same rear reversal; the ordinary constant amortized bound applies along a linear update history, not automatically to every adversarial branching workload.

Working Python program

python
class VersionedDispatchQueue:
    def __init__(self, front=None, rear=None, count=0):
        self.front = front
        self.rear = rear
        self.count = count

    @staticmethod
    def _reverse(chain):
        result = None
        while chain is not None:
            result = (chain[0], result)
            chain = chain[1]
        return result

    def _normalized(self):
        if self.front is not None or self.rear is None:
            return self
        return VersionedDispatchQueue(self._reverse(self.rear), None, self.count)

    def enqueue(self, case_id):
        next_version = VersionedDispatchQueue(self.front, (case_id, self.rear), self.count + 1)
        return next_version._normalized()

    def dequeue(self):
        ready = self._normalized()
        if ready.front is None:
            raise IndexError("dispatch queue is empty")
        case_id = ready.front[0]
        next_version = VersionedDispatchQueue(ready.front[1], ready.rear, ready.count - 1)
        return case_id, next_version._normalized()

    def values(self):
        front_values = []
        chain = self.front
        while chain is not None:
            front_values.append(chain[0])
            chain = chain[1]
        rear_values = []
        chain = self.rear
        while chain is not None:
            rear_values.append(chain[0])
            chain = chain[1]
        return front_values + rear_values[::-1]


if __name__ == "__main__":
    morning = VersionedDispatchQueue().enqueue(47).enqueue(19).enqueue(83)
    served_id, midday = morning.dequeue()
    afternoon = midday.enqueue(61)
    print("served:", served_id)
    print("morning:", morning.values())
    print("afternoon:", afternoon.values())

Output

Output
served: 47
morning: [47, 19, 83]
afternoon: [19, 83, 61]

Time, space, and tradeoff

Consing an enqueue or removing a ready front is O(1). Reversing a rear chain takes O(N) time and allocates O(N) new nodes on that operation; along one linear history, each enqueued item is reversed once, yielding O(1) amortized queue operations. A full values listing takes O(N). Retained versions keep referenced nodes alive, so memory grows with live history and branches. The two-list representation is much simpler than a real-time persistent queue, which is needed if a strict per-operation latency bound or heavy branching is required.

Common Mistakes

  • Do not mutate a node shared by an older version.
  • Do not claim worst-case constant time for a reversal.
  • Do not apply the linear-history amortized bound blindly to repeated branches.
  • Do not mistake a queue of IDs for a deep snapshot of mutable case records.

Connected lessons

Compare its update and query contract with Linear hashing: split one bucket at a time as a table grows, Compressed 2D Fenwick trees: toggle known points and count rectangles, Balanced-parentheses trees: encode an ordered hierarchy, then complete the structure audit and decision quiz.

data structures
stacks-and-queues
Storage details