Simple and Efficient Purely Functional Queues and Deques

Abstract

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 behaviour of certain functions on lazy lists.