efficient idiomatic queue?

[Alex Martelli]

"Paul Rubin" <phr-n2002a at nightsong.com> wrote in message
news:7xr8osorq1.fsf at ruckus.brouhaha.com...
> "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).

The "linear-time operation" in question is copying 1/2 of the current
list's contents, though.  Assume a sequence of N appends followed by
N pops: then we copy N/2 + N/4 + N/8 + ... = about N items in all, no?
Thus, O(N) times for N pops -> constant *amortized* time per pop.

I'm not totally confident about what happens for other ways to interleave
the appends and pops, admittedly.


Alex