Fully persistent lists with catenation
Fully persistent lists with catenation
复制标题
带串联的完全持久列表
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
James R. Driscoll;D. Sleator;R. Tarjan
本文考虑的问题，表示堆栈与连环，使任何堆栈，旧的或新的，可用于访问或更新操作。这个问题出现在基于列表和函数式编程语言的实现中。提出了一种解决方案，除了需要O（log log k）的时间和空间的连接，每个堆栈操作需要恒定的时间和空间。这里k是在连接之前完成的堆栈操作的数量。所有资源界限都在操作序列中摊销。
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.