Re: queue-length should be O(1) ? John Cowan 03 Dec 2014 13:19 UTC

Sven Hartrumpf scripsit:

> as queues are much more restricted than lists, it would
> be easy to store (and update) the queue-length in the underlying
> representation of the queue.

You trade off adding a mutation for every element added and removed to the
queue for speeding up queue-length.  I suspect that's not a good trade.
I suspect queue-empty? is far more likely to be used, and that's fast.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
If I have not seen as far as others, it is because giants were standing
on my shoulders.  --Hal Abelson