Clojure中的不可变队列

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

它只需要两个操作，入队和出队与通常的语义。

我认为是当然的名单和载体，但据我所知，他们的表现相对较差（即O（N）或更糟）进行修改，在年底分别开始 - 所以不理想的队列！

理想我想和O（log n）的两个入队和出队操作的适当的持久数据结构。

2010-06-28 mikera

为了避免人们写作如何使用缺点列表来实现推送/弹出栈（就像我差不多），不要忘记问题是关于* queues *。 :-) – 2010-06-28 22:05:08

刚刚注意到在最新的1.2快照Clojure Java源代码中有一个名为PersistentQueue的类....可能是我自己的问题的答案 – mikera 2010-06-28 22:09:07

它一直在那里，因为永远（刚刚检查过1.1，但我认为它比较老比起那个来说）。请注意，默认情况下不提供工厂函数和读取器语法;使用'clojure.lang.PersistentQueue/EMPTY'来获得一个空的实例。然后'conj'，'pop'和'peek'就像他们应该用一个队列一样工作。见例如我对这个问题的回答：http://stackoverflow.com/questions/2760017用'c.l.PQ'和Java'LinkedBlockingQueue'编写的代码。 – 2010-06-28 22:31:11

问题已解决 - 为其他人提供的解决方案可能会对您有所帮助。

我发现Clojure的有clojure.lang.PersistentQueue的类，它需要什么。

您可以创建这样一个实例：据我所看到的，你现在需要互操作使用Java创建实例，但作为米哈尔有益指出，你可以使用偷看，流行

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

然后连接。

来源

2010-06-28 22:46:23 mikera

PersistentQueue确实是您的最佳选择。为了将来的参考，下面是一张总结clojure数据结构的性能特征/保证的表格：http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html – dvogel 2010-06-29 05:37:27

为什么要使用'atom'？ – 2015-09-09 15:21:09

@ raxod502在这种情况下使用原子有什么问题吗？ – dgellow 2015-12-05 09:42:10

我用下面的函数queue创建PersistentQueue。或者，如果要打印和读取队列，您可能需要使用打印方法和数据读取器。

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

偷看 - 获得头
弹出 - 返回一个新的PersistentQueue无头
连词 - 添加项目到尾
空？ - 如果空
序列 - 内容作为一个序列（列表）


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

来源

2015-01-28 19:39:35 miner49r

Clojure中能真正从字面队列中受益。这将比依靠Java interop更清洁（并且更便于携带）。

但是，使用普通家庭项目（如列表）来推出自己的可移植持久队列并不难。

将队列看作两个列表，一个提供队列的头部分，另一个提供尾部。 enqueue添加到第一个列表中，dequeue从后者弹出。大多数ISeq函数都可以实现。

大概是唯一棘手的部分是当尾巴是空的，你想dequeue会发生什么。在这种情况下，头部列表为reverse d，并成为新尾部，空列表成为新头部列表。我相信，即使有reverse的开销，即enqueue和dequeue保持O(1)，虽然k将是当然比一个香草矢量更高。

快乐queue ing！

来源

2016-10-08 00:28:11 CurtainDog

Clojure中的不可变队列

回答

相关问题