# FIFO Data Structure in Python

This post is obselete, see this more recent discussion.

For some odd reason, Python doesn’t come with a good FIFO data structure (as of 2.4). Here’s one.

``` class Fifo: def __init__(self): self.data = [[], []] def append(self, value): self.data[1].append(value) def pop(self): if not self.data[0]: self.data.reverse() self.data[0].reverse() return self.data[0].pop() def __len__(self): return len(self.data[0])+len(self.data[1]) def tolist(self): temp= self.data[0][:] temp.reverse() return temp+self.data[1] ```

### Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

## 3 thoughts on “FIFO Data Structure in Python”

1. Because the expected popping time of your solution is linear with respect to the size of the list. Specifically, doing “del self.items[0]” can be tremendously expensive since Python needs to copy the entire array to a new location in memory. Doing so thousands of times is highly inefficient.

2. Why not try something simpler like this:

class Fifo:
def __init__(self):
self.items = []

def append(self, item):
self.items.append(item)

def pop(self):
item = self.items[0]
del self.items[0]
return item

def __len__(self):
return len(self.items)

def tolist(self):
#defensive copy
return self.items[:]

import unittest
class FifoTest(unittest.TestCase):
def testItemsArePoppedInSameOrderTheyWereRemoved(self):
fifo = Fifo()
fifo.append(‘a’)
fifo.append(‘b’)
fifo.append(‘c’)
self.assertEquals(‘a’, fifo.pop())
self.assertEquals(‘b’, fifo.pop())
self.assertEquals(‘c’, fifo.pop())

def testFifoLengthChangesAsItemsAreRemoved(self):
fifo = Fifo()
fifo.append(‘a’)
fifo.append(‘b’)
fifo.append(‘c’)
self.assertEquals(3, len(fifo))
fifo.pop()
self.assertEquals(2, len(fifo))
fifo.pop()
self.assertEquals(1, len(fifo))
fifo.pop()
self.assertEquals(0, len(fifo))

def testFifoCanBeConvertedToList(self):
fifo = Fifo()
fifo.append(‘a’)
fifo.append(‘b’)
fifo.append(‘c’)
self.assertEquals([‘a’,’b’,’c’], fifo.tolist())
if __name__ == ‘__main__’:
suite = unittest.TestSuite()