Thomas A. Russ <email@example.com> wrote:
| capitux <firstname.lastname@example.org> 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 Warnock <email@example.com>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607