Publication View

Simple and efficient purely functional queues and deques (1995)

Chris Okasaki

Abstract

We present purely functional implementations of queues and double-ended queues (deques) requiring only O(1) time per operation in the worst case. Our algorithms are considerably simpler than previous designs with the same bounds. The inspiration for our approach is the incremental behavior of certain functions on lazy lists.

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8825
Source	http://www.cs.columbia.edu/~cdo/jfp95.ps
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type	text
Language	English
Relation	10.1.1.42.1735, 10.1.1.55.5156, 10.1.1.48.9435, 10.1.1.13.3451, 10.1.1.12.3176, 10.1.1.46.571, 10.1.1.31.9642, 10.1.1.28.9377, 10.1.1.54.4293, 10.1.1.51.1461, 10.1.1.35.9196, 10.1.1.44.4874, 10.1.1.65.4699, 10.1.1.65.6908, 10.1.1.78.121, 10.1.1.95.473, 10.1.1.95.4869, 10.1.1.96.2612, 10.1.1.122.2786, 10.1.1.128.7539, 10.1.1.132.9179, 10.1.1.44.6725, 10.1.1.36.8323