adityar7 wrote:
> 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?
This is a very old technique for representing queues in functional
languages where you have no assignment. It's called immutable because
pointers are never changed once they're set.
In lisp you would have
;; car is back; cdr is front
(defun make-empty-queue () (cons nil nil))
(defun enqueue (item queue)
(cons
(cons item (car queue)) ;; add to back
(cdr queue))) ;; start of queue stays the same
(defun dequeue (queue)
(if (cdr queue)
(values (cadr queue) ;; first return value is head of front
(cons (car queue) ;; modified queue
(cddr queue)))
(if (car queue)
(dequeue (cons nil (reverse (car queue)))))))
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
