Purely functional, real-time deques with catenation

Haim Kaplan, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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 O(1) for each push, pop, inject, eject and catenation. The best previously known solution has an O(log* k) time bound for the fcth 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.

Original languageEnglish (US)
Pages (from-to)577-603
Number of pages27
JournalJournal of the ACM
Issue number5
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Catenation
  • Data structures
  • Double-ended queue
  • Persistent data structures
  • Purely functional data structures
  • Purely functional queues
  • Queue
  • Stack


Dive into the research topics of 'Purely functional, real-time deques with catenation'. Together they form a unique fingerprint.

Cite this