| Idea: |
- a persistent data structure never destroys information: every operation produces a new version, and all old versions remain readable (and here even writable — this stack is fully persistent)
- a stack is the easiest structure to make persistent, because push and pop can be implemented without modifying anything at all:
- represent the stack as a linked list; push allocates one new node pointing at the old top, and the new version is a pointer to that node — the old version still points where it did
- pop allocates nothing: the new version simply points one node further down the list
- the nodes shared by many versions form a tree growing up from the bottom: each version is one path from its pointer down to the bottom
|