Access Restriction

Author Kaplan, Haim ♦ Tarjan, Robert E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Catenation ♦ Data structures ♦ Double-ended queue ♦ Persistent data structures ♦ Purely functional data structures ♦ Purely functional queues ♦ Queue ♦ Stack
Abstract We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of catenable deques is required to add certain sophisticated programming constructs to functional programming languages. Our solution has a worst-case running time of $\textit{O}(1)$ for each push, pop, inject, eject and catenation. The best previously known solution has an $\textit{O}(log*\textit{k})$ time bound for the $\textit{k}th$ deque operation. Our solution is not only faster but simpler. A key idea used in our result is an algorithmic technique related to the redundant digital representations used to avoid carry propagation in binary counting.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 5
Page Count 27
Starting Page 577
Ending Page 603

Open content in new tab

   Open content in new tab
Source: ACM Digital Library