efficient idiomatic queue?

[David Eppstein]

In article <7xr8osorq1.fsf at ruckus.brouhaha.com>,
 Paul Rubin <phr-n2002a at nightsong.com> wrote:

> "Alex Martelli" <aleax at aleax.it> writes:
> > I think this should be constant-amortized-time,
> 
> I think logarithmetic amortized time, i.e. calling pop N times takes
> O(N log N) time (because it has to do a linear-time operation every so often).

No, Alex was right, it is constant amortized time.
Each linear time operation (reducing the list length)
can be charged against the insertion operations that added the items being 
removed from the list.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/