Clojure 中的双端队列

Question

Clojure中有双端队列吗？我的印象是 Clojure 的 PersistentQueue 是单端的（我错了吗？）。我需要能够从队列的任一端删除（即 "pop"）和 "peek" at 数据。双端队列的解释是 https://en.wikipedia.org/wiki/Double-ended_queue.

我看到 Java 有一个双端队列，但我不确定如何在 Clojure 中实例化队列对象。尝试创建一个新队列：

(java.util.Dequeue.)

给出错误：

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

Answer 1

Is there a double-ended queue in Clojure?

AFAIK 编号

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

最后只允许 conj，开头只允许 peek/pop。

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

您无法实例化 java.util.Queue because it's an interface. Have a look at the subinterface java.util.Deque 及其实现类:

例如，您可以按如下方式创建和使用 ArrayDeque：

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

(.pollFirst deque)
;;=> 1

但是，与其纠结于互操作语法和可变集合，不如查看 deque-clojure，它提供了 Clojure 中的持久实现。

Answer 2

为了完整起见，纯 Clojure 版本可能如下所示：

(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

Clojure 中的双端队列

Double-ended Queue in Clojure

queue

interop

clojure