[racket] Compound mutable list manipulation - 2 qs

>
> To get the best suggestions on alternative data structures you should
> say a little more about wha your program does and thus needs. However
> if all you're interested in is adding to the back and removing from
> the front, that is a queue, you can implement one using two lists
> without mutating the lists. One list represents the front and you can
> cdr down it efficiently, the other list represents the back in reverse
> and you cons elements onto it to add elements to the back of the
> queue. Whenever the front list becomes empty you reverse the back list
> to form the new front and the back becomes empty. This way you get a
> queue with O(1) amortized enqueue and dequeue operations.
>

That's an interesting approach, thanks for suggesting it, Marijn. I  
just wonder about the penalty of the reversal part and how it figures  
in?... I guess that it could be more or less neglectable provided  
there are few queues in which there are typically more adds than  
removals. However, in the application I'm working on (it's actually an  
emulation of an operating system using queues to manage task  
schedulers, event managers, interrupts and so on) there is no  
prediction whatsoever about the runtime behavior of the queues -  
there'll be nested queues, large queues, small queues, frequently  
accessed vs. mostly idle queues, queues more heavily removing than  
adding items and vice versa and so on. So in some of the queues there  
may be hefty swapping of queue fragments and efficiency may again  
become an issue. Another thing is that again quite some heavy burden  
is left on the garbage collector in this architecture which I'd like  
to avoid.

I'll implement both techniques (as Matthias pointed out, a good  
interface definition allows for easy replacement) and see if I can run  
some meaningful comparison tests.