Take the 2-minute tour ×

What's the best data structure for a fixed length stack (I originally called it a queue, but what I want is a stack) where items are added to the front, and every time an item is added to the front an item is removed from the end? Various lengths of subvectors will be accessed from the front also. I was using vectors, now thinking about clojure.lang.PersistentQueue and finger trees.

edit, to clarify, something like:

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

edit2: thanks for all your answers so far, this has turned into an exercise in going back to basics and reading Joy of Clojure, learning for instance that subvec of subvec retains a reference to the first subvec's vector, while something like (vec (cons x (subvec... would if used repeatedly accrue references to all intermediate subvecs. In light of this, how about this implementation of push for a vector-based queue ?:

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

then the resulting vector could be accessed via rseq which I believe is fast with vectors (due to its use of index-offset?)

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

Have a look at Amalloy's ring buffer at https://github.com/amalloy/ring-buffer

share|improve this answer
Dangit! Stealing my SO reputation by linking to my library? I kid, of course. Actually I'm curious how you found it, since I haven't advertised it at all and a google search for clojure ring buffer doesn't turn up anything terribly easily. –  amalloy Nov 13 '12 at 3:47
I found it in google at some point and now is in my bookmarks ;). Thanks! –  dAni Nov 13 '12 at 11:03
sorry to clarify, ring-buffer would be perfect if its items were added and peeked at the front and ejected from the end. It's the same problem I had with PersistentQueue: conj adds to the end but peek at the front, but I only care about most recent items (lifo) with oldest items being removed first –  Hendekagon Nov 14 '12 at 1:03
@amalloy - I've been trying ring buffer, & one thing I noticed is that in the source, some functions of IPersistentCollection are provided under IPersistentStack (empty and equiv) and that the provided cons implementation for IPersistentCollection (line 42) never seems to be called, as if I do (cons x rb) with a ring buffer, it returns a clojure.lang.Cons not a RingBuffer as the code suggests it would. Why is this ? –  Hendekagon Nov 15 '12 at 2:15
(cons x anything) returns a Cons, always. The cons method in java is the conj function in clojure. As for method ordering, it doesn't matter if those implementations go under IPC or IPS, because IPS extends IPC and therefore inherits all its method specifications. It's common to put them in the most-specific interface, because then you don't have to type as many interface names. –  amalloy Nov 15 '12 at 23:44
show 1 more comment

IMO you can use just a list:

(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)
        (reset! queue (take len new-items))
      (let [res (take-last len2 @queue)]
        (reset! queue (concat new-items
                              (drop-last len2 @queue)))


(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)
share|improve this answer
ok, but I was using vectors already. I don't see the need for an atom here –  Hendekagon Nov 13 '12 at 23:43
I missed last sentence of your question about vectors :) No, we need stm here. Furthermore, for thread safe solution we need ref instead of atom and make all work in dosync. –  mobyte Nov 14 '12 at 0:30
hmm, I would prefer a persistent structure –  Hendekagon Nov 14 '12 at 0:49
oh I just noticed you changed the implementation from vectors! I used vectors originally, but then discovered that subvec retains a reference to the original vector, which isn't gc'd, hence the need for an efficient persistent queue (maybe it's a stack what I seek?) –  Hendekagon Nov 14 '12 at 1:06
add comment

Your Answer


