efficient idiomatic queue?

[Alex Martelli]

"David Eppstein" <eppstein at ics.uci.edu> wrote in message
news:eppstein-B55AA6.08050515012002 at news.service.uci.edu...
> 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.

Hmmm, nice way to frame things, and it does come close to convincing
me that it's indeed constant amortized time for any interleaving of
append and pop operations.


Alex