Is there a purely functional implementation for a Bounded Queue with peek() in O(1)?

Question

I want to maintain an immutable bounded FIFO queue from which I can remove the oldest values after a certain time. In Scala, the immutable.Queue works well for size-bounded queues (.size seems to be O(N) since it's internally based on List, but I can maintain the size separately), but there seems to be no cheap way to access the head element to test the age of the oldest value with anything cheaper than O(N), so I cannot test the expiration state of the oldest entry. Any pointers to a purely functional (immutable) implementation?

Answer 1

This article, Haskell: Queues without pointers, describes a purely functional queue with O(1) amortized cost (edit: for adding and removing elements). I think the data structure comes from Chris Okasaki and more details are in his book.

The basic idea is to decompose the queue into two lists, one for the front and one for the back. New elements are added to "front". "Back" is stored in reverse order, to facilitate popping elements. When all elements of "back" are gone, "front" is reversed and re-identified as "back". This data structure has O(1) amortized cost for these operations, but apparently with some work it can be reduced to O(1), proper.

Edit: Okasaki's paper describes an elegant, purely functional implementation of queues and double-ended queues (deques). Deques allow adding or removing elements from either end. All such operations are O(1), worst case.