Double-ended Queue in Clojure

Question

Is there a double-ended queue in Clojure? My impression is Clojure's PersistentQueue is single ended (am I wrong?). I need to be able to remove (i.e. "pop") and "peek" at data from either end of the queue. An explanation of what I mean by a double-ended queue is https://en.wikipedia.org/wiki/Double-ended_queue.

I see that Java has a double-ended queue, but I'm unsure how to instantiate the queue object in Clojure. Tried creating a new queue with:

(java.util.Dequeue.)

Gives error:

No matching ctor found for interface java.util.Queue.

beatngu13 · Accepted Answer · 2017-01-10 08:53:39Z

Is there a double-ended queue in Clojure?

AFAIK no.

My impression is Clojure's PersistentQueue is single ended (am I wrong?).

It only allows conj at end and peek/pop from beginning.

I see that Java has a double-ended queue, but I'm unsure how to instantiate the queue object in Clojure.

You can't instantiate java.util.Queue because it's an interface. Have a look at the subinterface java.util.Deque and its implementing classes:

You can create and use, for instance, an ArrayDeque as follows:

(def deque (java.util.ArrayDeque. [1 2 3])) ;;=> 'user/deque (.pollFirst deque) ;;=> 1

However, rather than struggling with interop syntax and mutable collections, you may want to check out deque-clojure which offers a persistent implementation in Clojure.

Thanks a lot. Actually in my question I meant java.util.DeQueue rather than java.util.Queue. But, your answer holds regardless (I'll correct my question). Especially thanks for the suggestion of java.util.ArrayDeque (which provides an implementation for Deque). I had seen deque-clojure but hoped there was something simpler (I couldn't follow the code).

murphy · Accepted Answer · 2017-01-09 17:17:11Z

Just for completenes, a pure clojure version may look like this:

(defn deque ([] '[()()]) ([& elems] [elems '()])) (defn push-front [deque elem] (let [[head tail] deque] [(cons elem head) tail])) (defn push-back [deque elem] (let [[head tail] deque] [head (cons elem tail)])) (defn pop-front [deque] (let [[head tail] deque] (if (empty? head) [(-> tail reverse rest) head] [(rest head) tail]))) (defn pop-back [deque] (let [[head tail] deque] (if (empty? tail) [tail (-> head reverse rest)] [head (rest tail)]))) (defn peek-front [deque] (let [[head tail] deque] (if (empty? head) (-> tail reverse first) (first head)))) (defn peek-back [deque] (let [[head tail] deque] (if (empty? tail) (-> head reverse first) (first tail)))) ;; usage example: user> (let [dq (deque )] (-> dq (push-front :a) (push-front :b) (peek-back))) :a user> (let [dq (deque )] (-> dq (push-front :a) (push-front :b) (pop-back))) [() (:b)] user> (let [dq (deque )] (-> dq (push-back :a) (push-back :b) (peek-back))) :b

Collectives™ on Stack Overflow

Double-ended Queue in Clojure

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related