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]

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()
    suite.addTest(unittest.makeSuite(FifoTest))
    unittest.TextTestRunner(verbosity=3).run(suite)

Leave a Reply

Your email address will not be published. Required fields are marked *