2009/2/3 Konrad Hinsen <konrad.hin...@laposte.net>: > > Is there any reason to prefer lists over vectors or vice versa for > implementing queues? It seems that for both lists and vectors, adding > and removing at one end (front for lists, end for vectors) is cheap, > whereas it is expensive at the other end. For queues you need to add > at one end and remove from the other, so one of the two operations is > necessarily expensive. But is there a difference between the two?
You can use a pair of lists to implement a queue where the first list is used to dequeue items from and the second list is used to enqueue items to. When the first queue is empty, you replace it with a reversed version of the second queue. I don't have time to write this in clojure at the moment but in haskell it would be something like this: -- A queue consists of two lists of a's data Queue a = Queue [a] [a] -- i.e. when enqueueing we add the new item to the front of the second list enqueue (Queue as bs) i = Queue as (i:bs) -- when dequeueing we need to handle two cases: when A is emply and when A is not empty. In -- the first case we replace A with the reverse of B and replace B with the empty list, i.e. we -- move the enqueued elements from B to A and then run dequeue again with the new queue -- structure dequeue (Queue [] bs) = dequeue (Queue (reverse b) []) -- In the second case we simply return the head of A as the dequeued item and update the -- queue structure dequeue (Queue as bs) = (head as, Queue (tail as) bs) The point is that enqueueing and dequeueing are O(1) most cases and the reversing operation which is O(n) is amortised over the lifetime of the qeueue. > Konrad. -- ! Lauri --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
