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 firstname.lastname@example.org
If I have not seen as far as others, it is because giants were standing
on my shoulders. --Hal Abelson