CODEWITHSUNDEEP
clojurequeue
Hendekagon
Hendekagon

Reputation: 4643

Fixed length stack structure in Clojure

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

Upvotes: 9

Views: 1760

Answers (2)

mobyte
mobyte

Reputation: 3752

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

test:

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

Upvotes: 1

DanLebrero
DanLebrero

Reputation: 8593

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

Upvotes: 7

Related Questions