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。或者，如果您要打印和读取队列，您可能需要一个打印方法和一个数据读取器。

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

• peek -- 获取头部
• pop -- 返回一个没有头部的新 PersistentQueue
• conj -- 将项目添加到尾部为
• 空？ -- 如果为空则为 true
• 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])))))

Answer 3

Clojure 确实可以从队列文字中受益。这比依赖 Java 互操作更干净（并且更可移植）。

然而，创建自己的便携式持久队列并不难，只需使用列表等普通家庭用品即可。

将队列视为两个列表，一个提供队列的头部，另一个提供队列的尾部。 enqueue 添加到第一个列表，dequeue 从后者弹出。大多数ISeq 函数都是简单实现的。

也许唯一棘手的部分是当尾部为空并且您想要出队时会发生什么。在这种情况下，头列表将被reversed并成为新的尾部，而空列表将成为新的头列表。我相信，即使有反向的开销，enqueue和dequeue仍然是O(1)，不过当然，k 会比普通向量更高。

快乐排队！