CODEWITHSUNDEEP
clojurequeueinterop
DarrylG
DarrylG

Reputation: 17166

Double-ended Queue in Clojure

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.

Upvotes: 3

Views: 1305

Answers (2)

beatngu13
beatngu13

Reputation: 9393

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.

Upvotes: 7

murphy
murphy

Reputation: 544

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

Upvotes: 3

Related Questions