Hi,
Recently I found an algorithm for creating a Queue datatype whose
objects are immutable. Basically, the algorithm is as follows:
class ImmutableQueue {
// Assume we know how to create immutable lists
ImmutableList back;
ImmutableList front;
...
}
The queue is broken into two. Elements at the front of the queue appear
in the list 'front' in natural order. Elements at the back of the queue
appear in the list 'back' in reversed order. So the entire queue would
be the [q.front ^ reverse(q.back)].
To enqueue an element, we simply cons it to the 'back' list. To dequeue
an element, we take it off the 'front' list, and replace the 'back'
list by the empty list.
Now, I have two questions:
1. If we have 'enqueue' and 'dequeue' operations as described above,
how is the queue still immutable?? I mean, those operations do change
the queue right? I must be missing something.
2. What is the purpose of such an immutable queue? Anyone ever come
across (or can think of) any uses?
Thanks
-Aditya
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
