Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there such a thing as an associative queue?

Tags:

clojure

I want a clojure data structure that:

  • pops from the front
  • pushes to the rear
  • lets me assoc indices with values (i.e. (assoc q 0 1) would set the value of the front to 1)

Is there something like that in Clojure (unfortunately PersistentQueue doesn't fulfill Nr.3), or should I built it on top of vector?

like image 230
Cubic Avatar asked Oct 26 '12 05:10

Cubic


People also ask

What is the difference between queue and associative array?

The key difference between a queue and an associative array is how individual elements are added or removed. You have to explicitly "push" to allocate elements to the front or back of a queue, and the elements are always indexed with a value from 0 at the front to the size of the queue minus 1 at the back.

What is the difference between associative and dynamic array?

Associative array SystemVerilog When the size of the collection is unknown or the data space is sparse, an associative array is a better option. Dynamic arrays are useful for contiguous collections of variables whose number changes dynamically.

Which is an example of an associative array?

The most frequently used general purpose implementation of an associative array is with a hash table: an array combined with a hash function that separates each key into a separate "bucket" of the array.

What is the difference between mailbox and queue?

A queue is just a data structure, and a mailbox is an higher level concept that is built around a combination of queues and semaphores. If you have only one process reading and writing to the data structure, there is no need to use a mailbox.

What is the difference between dynamic array and queue?

Queue has a dynamic and fixed size. Array has a fixed size. Stack has a dynamic and fixed size. Queue can contain elements of different data type.


2 Answers

There isn't a data structure in standard Clojure that will meet these requirements efficiently.

There was some talk on the Clojure-Dev mailing list about using RRB trees for vectors, which would be a great data structure for this:

  • https://groups.google.com/forum/?fromgroups=#!topic/clojure-dev/xnbtzTVEK9A

Not sure how far that has developed - but if you are interested in this kind of data structure then it is definitely worth taking a look at this.

like image 89
mikera Avatar answered Oct 08 '22 07:10

mikera


If you do not require persistency of the data structure, you could use java.util.LinkedList in your Clojure programs.

Example:

;;; Creation
user> (import 'java.util.LinkedList)
java.util.LinkedList
user> (def linked-list (LinkedList. [:a :b :c :d :e]))
#'user/linked-list

;;; Pop from the front
user> (.pop ^LinkedList linked-list)
:a
user> linked-list
#<LinkedList [:b, :c, :d, :e]>

;;; Push to the rear, but costly
user> (.addLast ^LinkedList linked-list :x)
nil
user> linked-list
#<LinkedList [:b, :c, :d, :e, :x]>

;;; Assoc (cf. (assoc linked-list 0 :y)
user> (.add ^LinkedList linked-list 0 :y)
nil
user> linked-list
#<LinkedList [:y, :b, :c, :d, :x]>
like image 27
tnoda Avatar answered Oct 08 '22 09:10

tnoda