efficient idiomatic queue?

[Huaiyu Zhu]

On Tue, 15 Jan 2002 09:46:51 +0100, Alex Martelli <aleax at aleax.it> wrote:
>
>What about (warning, untested and particularly un-profiled code):
>
>class fifo:
>    def __init__(self):
>        self.data = []
>        self.first = 0
>    def head(self):
>        return self.data[self.first]
>    def pop(self):
>        self.first += 1
>        if self.first > len(self.data)/2:
>            self.data = self.data[self.first:]
>            self.first = 0
>    def append(self, value):
>        self.data.append(value)
>
>I think this should be constant-amortized-time, and never take more
>space than K+2*N where N is the number of items in the list at a
>given time.  It may be possible to find sequences of pop and append
>operations that degrade per-operation time beyond amortized constant.

This can be extended to a fancier scheme, where you can save quite some
append and del if you also keep an attribute self.last and let the fifo wrap
around on the list.  It is simple to implement in Python due to the way
negative indices are treated.  In the following diagram * represents element
in the queue and . represents dummy element:

...... first ******** last ......
**** last .......first *********

When self.last catches up on self.first, the list size is enlarged, say, by
a factor of 0.2.  It is reduced by a factor when the queue falls under a
certain proportion of the list.  These factors represent the trade-off
between space and speed.  This scheme is more useful when there are lots of
appned and pop but the queue length remains fairly stable, in which case the
cost of list changing operations approach zero-amortized time.

Huaiyu