[Python-Dev] FIFO data structure?

[Tim Peters]

[Agthorr]
> I actually just wrote a modification to Queue that is O(1).  There's
> no change to the interface, so it doesn't require adding a new data
> structure.
>
> I have the code here:
>     http://www.cs.uoregon.edu/~agthorr/Queue.py
>
> The only changes are near the bottom of the file, beginning with the
> _init() function.  My implementation uses Python lists, but it uses
> them in a smarter way than the existing Queue implementation.
>
> I'll submit a patch to SourceForge in a day or two.

I'm opposed to this.  The purpose of Queue is to mediate communication among
threads, and a Queue.Queue rarely gets large because of its intended
applications.  As other recent timing posts have shown, you simply can't
beat the list.append + list.pop(0) approach until a queue gets quite large
(relative to the intended purpose of a Queue.Queue).

If you have an unusual application for a Queue.Queue where it's actually
faster to do a circular-buffer gimmick (and don't believe that you do before
you time it), then, as the comments say, you're invited to *subclass*
Queue.Queue, and override as many of the six queue-implementation methods at
the bottom of the class as you believe will be helpful.  It's not helpful to
change the *base* implementation of Queue.Queue for an O() advantage swamped
by increased overhead at typical queue sizes.