Cấu trúc ngăn xếp chiều dài cố định ở Clojure

Question

Cấu trúc dữ liệu tốt nhất cho ngăn xếp chiều dài cố định (ban đầu tôi gọi nó là hàng đợi, nhưng thứ tôi muốn là ngăn xếp), nơi các mục được thêm vào mặt trước và mỗi lần thêm mục phía trước một mục được lấy ra từ đầu? Chiều dài khác nhau của subvectors sẽ được truy cập từ phía trước cũng. Tôi đã sử dụng vectơ, bây giờ nghĩ về clojure.lang.PersistentQueue và cây ngón tay.

chỉnh sửa, để làm rõ, một cái gì đó như:

> (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: cảm ơn cho tất cả các câu trả lời của bạn cho đến nay, điều này đã trở thành một bài tập trong sẽ trở lại vấn đề cơ bản và đọc Joy của Clojure, học tập ví dụ mà subvec của subvec giữ lại một tham chiếu đến vector của subvec đầu tiên, trong khi một cái gì đó như (vec (cons x (subvec ... sẽ nếu được sử dụng liên tục tích luỹ các tham chiếu tới tất cả các subvec trung gian). hàng đợi dựa trên?:

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

thì vector kết quả có thể được truy cập thông qua rseq mà tôi tin là nhanh với vectơ (do sử dụng các chỉ số bù đắp?)

Answer 1

Có một cái nhìn tại vòng đệm Amalloy tại https://github.com/amalloy/ring-buffer

Answer 2

IMO bạn có thể sử dụng chỉ một danh sách:

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

kiểm tra:

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