Struttura stack in lunghezza fissa in Clojure

Question

Qual è la migliore struttura dati per uno stack di lunghezza fissa (inizialmente l'ho chiamato una coda, ma quello che voglio è uno stack) dove gli elementi vengono aggiunti in primo piano e ogni volta che viene aggiunto un elemento in primo piano un oggetto viene rimosso dalla fine? Si accede anche a varie lunghezze di subvettori dalla parte anteriore. Stavo usando i vettori, ora penso a clojure.lang.PersistentQueue e finger trees.

modificare, per chiarire, qualcosa come:

> (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: grazie per tutte le vostre risposte finora, questo è trasformato in un esercizio di tornare alle origini e la lettura di Gioia del Clojure, imparando per esempio che subvec di subvec mantiene un riferimento al vettore del primo subvec, mentre qualcosa del genere (vec (cons x (subvec ... sarebbe se usato ripetutamente accresca i riferimenti a tutti i subvec intermedi.) Alla luce di questo, che ne dici di questa implementazione di push per un vettore -based queue?:

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

allora il vettore risultante è stato possibile accedere tramite rseq che credo sia veloce con vettori (conseguente al suo impiego dell'indice-offset?)

Answer 1

Dai un'occhiata alla buffer circolare di Amalloy a https://github.com/amalloy/ring-buffer

Answer 2

IMO è possibile utilizzare solo un elenco:

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

prova:

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