efficient idiomatic queue?

[Raymond Hettinger]

"Delaney, Timothy" <tdelaney at avaya.com> wrote in message
news:mailman.1011232764.16285.python-list at python.org...
>
> 10000    <type 'list'>        0.329070
> 10000    <type 'array'>       0.234557
> 10000    DictIntFifo          0.123809
> 10000    DictLongFifo         0.185284
> 10000    ListPrependFifo      0.329698
> 10000    ListAppendFifo       0.398269
>
> 100000   <type 'list'>        76.195043
> 100000   <type 'array'>       56.828019
> 100000   DictIntFifo          1.269020
> 100000   DictLongFifo         1.961017
> 100000   ListPrependFifo      60.693928
> 100000   ListAppendFifo       77.094517
>
> So once you get to decently large quantities in the queue, the dict
versions
> make real sense over a basic list (Win2000).
>
> Tim Delaney


Before drawing a conclusion on this one, please add Sébastien Keim's
approach
to the mix:

class NestedListFifo:
 def __init__(self):
  self.first=[]
 def append(self,data):
  node = [data,[]]
  if self.first == []:
   self.first= node
  else:
   self.last[1] = node
  self.last = node
 def pop(self, n=-1):
  node = self.first
  self.first=node[1]
  return node[0]

Raymond Hettinger