John Smith <johnny@der.com> wrote:
+---------------
| what if I'd keep the length of the dequeue in a statevariable and acces the
| second-last pair through list-ref? would it cdr down the whole list or acces
| the 2nd-last pair directly?
+---------------

"List-ref" necessarily CDRs down the whole list, since a list cannot be
randomly addressed.  (A *vector* can be randomly addressed, but unlike a
list it cannot [in Scheme] be extended without copying the whole vector.)

You need to think a little more about the implications of the definition
given in SICP of the term "dequeue" -- DOUBLE-ended queue. One of the most
common ways of implementing a dequeue is with a DOUBLY-linked list.

Now compare that with an ordinary list, also known as a SINGLY-linked list,
which can trivially be used to implement a stack, and can almost as easily
be used to implement a SINGLE-ended queue.

If this isn't a sufficient hint, perhaps you should go read Knuth's
"The Art of Computer Programming", Volume I, Chapter 2, "Information
Structures", which discusses stacks, queues, and deques (another spelling
of dequeue) in great detail...


-Rob

-----
Rob Warnock, 8L-846		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		FAX: 650-933-0511
Mountain View, CA  94043	PP-ASEL-IA