Thomas A. Russ <tar@sevak.isi.edu> wrote:
+---------------
| capitux <capitux@tiscali.it> writes:
| > I am a beginner in lisp, I should do a program lisp that creates a 
| > circular list.  I have to then to introduce and to eliminate item in the 
| > list according to the FIFO policy.  Someone it can help me?
| 
| It isn't at all clear to me what a FIFO policy would mean for a list
| that is circular.  With a circular list you, by definition, have no
| beginning or end of the list, so where do you decide the place in the
| list to add or remove items?
| 
| I'm wondering if there is some terminologic confusion in your problem
| statement and that instead of a circular list, you really mean something
| like a queue -- for which FIFO makes a lot of sense.
+---------------

Actually, there *is* a well-known (I'm almost tempted to say "ancient"!)
algorithm for implementing the storage for a FIFO as a circular list
with only one "pointer" into it. [IIRC, it's in Knuth's "AoCP" vol.1,
ch.2: "Data Structures".]

Homework spoiler hint for the OP: The value of the FIFO "object" should
be the cons which is the *last* item in the FIFO, not the first. This
will permit the proper enqueue & dequeue operations to be implemented
in constant time with only one "pointer" into the circular list.

[Hopefully, Thomas will find the implications of this obvious,
while still leaving some work to do for the student's homework. ;-}  ;-} ]


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607