Jim Rees scripsit:

> Yes.   Any plausible implementation that meets the requirements has a
> representation that is symmetric with respect to "front" and "back".   Ie.
> if there is a lazy-sequence or stream for the front, there's one just like
> it on the back.
>
> The reversal algorithm just constructs a new ideque containing the source
> components flipped.   There is no other work to be done.

Indeed, a simple two-Lisp-list (no laziness) implementation has the same
property:  there is a list of elements at the front and another, reversed,
list of elements at the back.  Reversing the whole deque is just what
you say it is.  However, popping is only asymptotically O(1) in such an
implementation, because when you are trying to pop from the {back,front}
and it is empty, you need to reverse the elements in the {front,back} --
however, this O(n) operation happens just once during the life of the
deque on average, so its cost can be amortized over all the O(1) pops.
There are clever tricks for lowering the constant, such as reversing
only some of the elements, but I think they are hardly worth it.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
"Repeat this until 'update-mounts -v' shows no updates.
You may well have to log in to particular machines, hunt down
people who still have processes running, and kill them."