Clojure中的不可变队列

Question

在Clojure中获取简单,高效的不可变队列数据类型的最佳方法是什么？

它只需要两个操作,用通常的语义排队和出列.

我当然考虑过列表和向量,但我知道它们在结尾和开始时的性能相对较差(即O(n)或更差) - 因此不适合排队!

理想情况下,我想要一个适当的持久数据结构,其中包含入队和出队操作的O(log n).

Answer 1

问题解决了 - 可能会发现它有用的其他人的解决方案.

我发现Clojure有clojure.lang.PersistentQueue类可以完成所需的操作.

您可以创建这样的实例:

(def x (atom clojure.lang.PersistentQueue/EMPTY))

据我所知,您目前需要使用Java互操作来创建实例,但正如Michal所指出的那样,您可以随后使用peek,pop和conj.

Answer 2

我使用以下函数queue来创建PersistentQueue.或者,如果您打算打印并读取队列,则可能需要打印方法和数据读取器.

已经为PersistentQueue实现了通常的Clojure函数.

• 偷看 - 抓住头脑
• pop - 返回一个没有头部的新PersistentQueue
• conj - 将项目添加到尾部
• 空？ - 如果为空则为真
• seq - 作为序列的内容(列表)

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