FULLY PERSISTENT LISTS WITH CATENATION

被引：14

作者：

DRISCOLL, JR

SLEATOR, DDK

TARJAN, RE

机构：

[1] CARNEGIE MELLON UNIV,SCH COMP SCI,PITTSBURGH,PA 15213

[2] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08540

[3] NEC RES INST,PRINCETON,NJ 08540

来源：

JOURNAL OF THE ACM | 1994年 / 41卷 / 05期

关键词：

ALGORITHMS; DESIGN; LANGUAGES; THEORY; AMORTIZATION; CATENATION; CONCATENATION; DATA STRUCTURES; FUNCTIONAL PROGRAMMING; LISP; LIST; QUEUE; STACK;

D O I：

10.1145/185675.185791

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：943 / 959

页数：17