efficient idiomatic queue?

[Alex Martelli]

"David Eppstein" <eppstein at ics.uci.edu> wrote in message
news:eppstein-27FE15.16175514012002 at news.service.uci.edu...
> What is the idiomatic way in Python of implementing the following
> operations on a list of elements:
>  - return the element at the front of the list, without changing the list
>  - remove the element from the front of the list
>  - add a new element to the rear of the list
>
> My first choice would be L[0], del L[0], and L.append(), however it
> seems from some brief experiments that the del operation takes time linear
> in the length of the list, so this would be very inefficient for long
> lists. I also tried replacing the del with L=L[1:] but that wasn't any
> better.  A third possibility would be to have to variables L and i, and
> implement the three operations with L[i], i=i+1, and L.append(), which is
> fast but not good in space usage when the total number of operations is
> much larger than the length of the list.
>
> Is there a simple Pythonic way of implementing these three operations in
> constant (amortized) time per operation and space linear in the length of
> the list?

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.

Such anomalies, in similar cases, are generally ameliorated by some
further guard against too much churning in the data structure, e.g.
    if self.first>self.Konstant and self.first>len(self.data)/2:
as the guard-clause for the self.data rebinding -- any constant
value self.Konstant will not matter asymptotically in terms of
space taken, of course (it goes into the K of "K+2*N").


Alex