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.

To save someone from writing about how cons lists can be used to implement push/pop stacks (like I almost did), don't forget the question asks about *queues*. :-) — Joey Adams, Jun 28 '10 at 22:05
Just noticed there is a class called PersistentQueue in the latest 1.2 snapshot Clojure Java source.... may be the answer to my own question — mikera, Jun 28 '10 at 22:09
It's been in there since forever (just checked with 1.1, but I think it's older than that). Note that there's no factory function nor reader syntax for it provided by default; use `clojure.lang.PersistentQueue/EMPTY` to get an empty instance. Then `conj`, `pop` & `peek` work as they should with a queue. See e.g. my answer to this question: http://stackoverflow.com/questions/2760017 for some code written with both `c.l.PQ` and Java's `LinkedBlockingQueue`. — Michał Marczyk, Jun 28 '10 at 22:31
Cool, thanks Michal! I guess I missed it at first because there wasn't a simple "queue" constructor in the API. Maybe I should submit a patch :-) — mikera, Jun 28 '10 at 22:50
`PersistentQueue` is indeed one of Clojure's more closely guarded secrets. ;-) About possible queue-related API enhancements, see this thread on Clojure Dev: http://groups.google.com/group/clojure-dev/browse_thread/thread/e0fad47532028e99 Note that's probably a very low-priority matter right now, what with the new numerics and all... — Michał Marczyk, Jun 28 '10 at 23:05

mikera · Accepted Answer · 2010-06-28T22:51:27.117

37

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.

edited Jun 28 '10 at 22:51

answered Jun 28 '10 at 22:46

mikera

105,238
25
256
415

6

PersistentQueue is indeed your best option. For future reference, here is a table summarizing the performance characteristics/guarantees of clojure data structures: http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html – dvogel Jun 29 '10 at 05:37
@raxod502 Is there something wrong with the use of an atom in this situation? – dgellow Dec 05 '15 at 09:42
@dgellow From my understanding, using atoms in functional programming languages is a Bad Sign unless there's a good reason for it -- everything is generally supposed to be immutable. – Resigned June 2023 Dec 05 '15 at 16:55
@RadonRosborough, ...however, it's definitely better practice to have an atom inside a Var than to mutate the Var itself. Which is to say, *if* you're going to use `def` (which isn't always necessary, granted!) to put a name to something other than a constant, then an appropriately-chosen reference type is typically the right thing to associate with it. – Charles Duffy Apr 25 '17 at 00:59
@CharlesDuffy You're certainly right. The only reason I commented was because there was nothing in the question that suggested STM or mutable state was desired, so I found it very odd that the answer used an `atom` for no apparent reason. – Resigned June 2023 Apr 25 '17 at 01:33

score 9 · Answer 2 · answered Jan 28 '15 at 19:39

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])))))

score 1 · Answer 3 · answered Oct 08 '16 at 00:28

Clojure could really benefit from a queue literal. This would be cleaner (and more portable) than relying on Java interop.

However, it's not that hard to roll your own portable persistent queue, just using ordinary household items like lists.

Consider the queue as two lists, one providing the head portion of the queue, and the other the tail. enqueue adds to the first list, dequeue pops from the latter. Most ISeq functions are trivially implemented.

Probably the only tricky part is what happens when the tail is empty and you want to dequeue. In that case the head list is reversed and becomes the new tail, and the empty list becomes the new head list. I believe, even with the overhead of the reverse, that enqueue and dequeue remain O(1), though the k is going to be higher than a vanilla vector of course.

Happy queueing!

Immutable queue in Clojure

3 Answers3