J. R. Driscoll, D. D. Sleator, R. E. Tarjan, Fully Persistent Lists with Catenation, Journal of the Association for Computing Machinery. Vol 41. No 5, September 1994. pp. 943–959
This paper considers the problem of representing stacks with catenation so that any
stack, old or new, is available for access or update operations. This problem arises in the
implementation of list-based and functional programming languages. A solution is proposed
requiring constant time and space for each stack operation except catenation, which requires
O(log log k) time and space. Here k is the number of stack operations done before the
catenation. All the resource bounds are amortized over the sequence of operations.