efficient idiomatic queue?

[David Eppstein]

In article <mailman.1011111645.10873.python-list at python.org>,
 "Jason Orendorff" <jason at jorendorff.com> wrote:

> > I'm not sure what you mean by quick enough, but when I tried draining a
> > list by repeated del L[0], on lists of 10000 elements it took roughly a
> > second -- more time than I'd like to spend in most interactive situations.
> 
> All you had to say was, "5000 items won't do it for me.  I want
> genuine O(N log N) behavior."

I didn't say it that way because I think it's important to understand why 
good asymptotics are important, and under what circumstances it would be ok 
to use slower algorithms, rather than just blindly using the math.

Anyway, thanks for all the solutions posted so far.
The reverse trick is looking cleanest for merge sort, although Alex M.'s 
queue implementation looks good (better I think than the more obvious 
linked list version) and I also like the ADT-ized generator version.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/