8

固定长度堆栈（我最初将其称为队列，但我想要的是堆栈）的最佳数据结构是什么，其中项目被添加到前面，并且每次将项目添加到前面时，都会从结尾？也可以从前面访问各种长度的子向量。我正在使用向量，现在考虑 clojure.lang.PersistentQueue 和手指树。

编辑，澄清，类似：

> (def q (queue [1 2 3 4]))
[1 2 3 4]
> (push q 9 8 7)
[7 8 9 1]
> (peek (push q 9 8 7))
7

编辑2：感谢您到目前为止的所有回答，这已经变成了回归基础和阅读 Clojure 的乐趣的练习，例如学习 subvec 的 subvec 保留对第一个 subvec 向量的引用，而类似 (vec (cons x (subvec... 如果重复使用会累积对所有中间 subvec 的引用。鉴于此，对于基于向量的队列的推送实现如何？：

(defn push [v i n] (if (>= (count v) n) (conj (subvec v 1 n) i) (conj v i) ) )

然后可以通过 rseq 访问得到的向量，我认为这对向量来说很快（由于它使用了索引偏移量？）

4

2 回答 2

6

在https://github.com/amalloy/ring-buffer查看 Amalloy 的环形缓冲区

于 2012-11-12T23:48:11.420 回答
1

IMO 你可以只使用一个列表：

(defn create-queue [len]
  (atom (repeat len nil)))

(defn push [queue new-items]
  (let [len (count @queue)
        len2 (count new-items)]
    (if (>= len2 len)
      (let [res (concat (take-last (- len2 len) new-items)
                        @queue)]
        (reset! queue (take len new-items))
        res)
      (let [res (take-last len2 @queue)]
        (reset! queue (concat new-items
                              (drop-last len2 @queue)))
        res))))

测试：

(def q (create-queue 4))

(take 4 @q)
-> (nil nil nil nil)
(push q [1 2 3])
-> (nil nil nil)
(take 4 @q)
-> (1 2 3 nil)
(push q [4 5])
-> (3 nil)
(take 4 @q)
-> (4 5 1 2)
(push q [6 7 8 9])
-> (4 5 1 2)
(take 4 @q)
-> (6 7 8 9)
(push q [10 11 12 13 15 16])
-> (15 16 6 7 8 9)
(take 4 @q)
-> (10 11 12 13)
于 2012-11-13T04:14:32.467 回答