Immutable queue in Clojure

Question

What is the best way to obtain a simple, efficient immutable queue data type in Clojure?

It only needs two operations, enqueue and dequeue with the usual semantics.

I considered lists and vectors of course, but I understand that they have comparatively poor performance (i.e. O(n) or worse) for modifications at the end and beginning respectively - so not ideal for queues!

Ideally I'd like a proper persistent data structure with O(log n) for both enqueue and dequeue operations.

Answer 1

Problem solved - solution for others who may find it helpful.

I've found that Clojure has the clojure.lang.PersistentQueue class that does what is needed.

You can create an instance like this:

(def x (atom clojure.lang.PersistentQueue/EMPTY))

As far as I can see, you currently need to use the Java interop to create the instance but as Michal helpfully pointed out you can use peek, pop and conj subsequently.