[Tutor] a FIFO with fixed capacity?
dyoo at hkn.eecs.berkeley.edu
Thu Mar 31 11:19:24 CEST 2005
On Wed, 30 Mar 2005, Marcus Goldfish wrote:
> I need to implement a FIFO with a fixed maximum capacity.
Out of curiosity, why do you require a first-in-first-out queue with a
> 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:
is similar to a nicer one by Jeremy Fincher:
__slots__ = ('back',)
self.back = 
def enqueue(self, elt):
self[:] = self.back
self.back = 
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:
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!
More information about the Tutor