It needn't be especially fancy. Here is what I had in mind:
n = 50 class fifo(object):
def __init__(self): # block[0:n] is for data and block[n] is a link field self.head = self.tail = [None] * (n+1) self.headptr = self.tailptr = 0 ...etc...
I've got a few of the standard FIFO implementations sitting here, and I thought I would give them a run against each other. Testing methods are as follows: Initially create a FIFO of n elements. Alternate between pushing and popping 2n elements from the FIFO. Empty the FIFO. Timing each block, we get the following: Create Steady Empty n = 10000: Fifo 0.047 0.328 0.141 Fifo_list 0.171 0.485 0.14 fast_list_fifo 0.0 0.297 0.157 doublelistfifo 0.0 0.359 0.172 fifo_raymond 0.109 0.422 0.172 n = 20000: Fifo 0.093 0.657 0.297 Fifo_list 0.375 0.984 0.266 fast_list_fifo 0.0 0.594 0.312 doublelistfifo 0.0 0.719 0.344 fifo_raymond 0.203 0.859 0.329 n = 30000: Fifo 0.157 0.984 0.437 Fifo_list 0.563 1.453 0.422 fast_list_fifo 0.0 0.89 0.469 doublelistfifo 0.016 1.078 0.515 fifo_raymond 0.297 1.297 0.5 n = 40000: Fifo 0.203 1.328 0.594 Fifo_list 0.984 1.953 0.594 fast_list_fifo 0.015 1.188 0.625 doublelistfifo 0.0 1.437 0.687 fifo_raymond 0.438 1.734 0.656 Fifo: dictionary used as a fifo fifo_list: [cur, [next, [...]]] fast_list_fifo: push appends, pop increments a pointer, but never removes element doublelistfifo: self explanatory fifo_raymond: the fifo described by raymond. Initialization for Raymond's fifo can be ignored, it is merely inserting objects one at a time (I am short on time this evening). Interpret the rest of the numbers as is reasonable, but consider that there is likely a few percent margin of error on each number, unless something always beats another. I must be going to bed now, the wife is yelling at me. - Josiah