[Tutor] a FIFO with fixed capacity?

[Danny Yoo]

On Wed, 30 Mar 2005, Marcus Goldfish wrote:

> I need to implement a FIFO with a fixed maximum capacity.

Hi Marcus,

Out of curiosity, why do you require a first-in-first-out queue with a
maximum capacity?


> Would limiting the max capacity of the FIFO improve performance by
> allowing one to preallocate the FIFO buffer?

Possibly, but at the cost of having a FIFO that can get full.  Depending
on the domain, this might be ok for you.  But most programs suffer from
hardcoded limits that really shouldn't have been hardcoded in the first
place.  You may want to see if having a queue with unlimited size is
really a performance drag on your system: have you done any profiling yet?


The second implementation that you quoted earlier:

> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/210459

is similar to a nicer one by Jeremy Fincher:

######
class ListSubclassFifo(list):
    __slots__ = ('back',)
    def __init__(self):
        self.back = []
    def enqueue(self, elt):
        self.back.append(elt)
    def dequeue(self):
        if self:
            return self.pop()
        else:
            self.back.reverse()
            self[:] = self.back
            self.back = []
            return self.pop()
######

(See: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436)

Since these implementations guarantee O(1) "constant" time access for a
queue, even without a hardcoded bound limit, you aren't losing much.  Can
you use this implementation?


Finally, there's a 'deque' in the 'collections' Standard Library module
that you might be able to use:

    http://www.python.org/doc/lib/module-collections.html

which also should define constant-time guarantees for insertion and
removal.  So you might just be able to use that, and not have to
copy-and-paste any code at all.  *grin*


Best of wishes to you!