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.

Answer 2

I use the following function queue to create a PersistentQueue. Optionally, you might want to have a print-method and a data-reader if you're going to be printing and reading the queues.

The usual Clojure functions are already implemented for PersistentQueue.

• peek -- get the head
• pop -- returns a new PersistentQueue without the head
• conj -- add item to the tail
• empty? -- true if empty
• seq -- contents as a sequence (list)

     (defn queue       ([] clojure.lang.PersistentQueue/EMPTY)       ([coll] (reduce conj clojure.lang.PersistentQueue/EMPTY coll)))      (defmethod print-method clojure.lang.PersistentQueue       [q ^java.io.Writer w]       (.write w "#queue ")       (print-method (sequence q) w))      (comment        (let [*data-readers* {'queue #'queue}]          (read-string (pr-str (queue [1 2 3])))))