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

edit2：これまでのすべての回答に感謝します。これは、基本に戻ってJoy of 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を介してアクセスできます。これは、ベクトルを使用すると高速であると私は信じています（index-offsetを使用しているためですか？）

4

2 に答える 2

6

https://github.com/amaloy/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 に答える