| Catenable Double-Ended Queues (1997) | |||||||||||||||||
Abstract | |||||||||||||||||
| Catenable double-ended queues are double-ended queues (deques) that support catenation (i.e., append) efficiently without sacrificing the efficiency of other operations. We present a purely functional implementation of catenable deques for which every operation, including catenation, takes O(1) amortized time. Kaplan and Tarjan have independentlydevelopeda much more complicated implementation of catenable deques that achieves similar worst-case bounds. The two designs are superficially similar, but differ in the underlying mechanismused to achieve efficiency in a persistent setting (i.e., when used in a non-single-threaded fashion). Their implementation uses a technique called recursive slowdown, while ours relies on the simpler mechanism of lazy evaluation. Besides lazy evaluation, our implementation also exemplifies the use of two additional language features: polymorphic recursion and views. Neither is indispensable, but both significantly simplify the presentation. 1 Introduction ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||