algorithm - 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。