Python Cookbook

Implementing a First-In First-Out Container

Credit: Sébastien Keim

Problem

You need a container that allows element insertion and removal, in which the first element inserted is also the first to be removed (i.e., a first-in first-out, FIFO, queue).

Solution

We can use a class to wrap a Pythonic implementation of a linked list:

class Fifo:
    def _ _init_ _(self):
        self.first = None
        self.last = None
    def append(self, data):
        node = [data, None]  # [payload, 'pointer'] "pair"
        if self.first is None:
            self.first = node
        else:
            self.last[1] = node
        self.last = node
    def pop(self):
        if self.first is None :
            raise IndexError
        node = self.first
        self.first = node[1]
        return node[0]

if _ _name_ _=='_ _main_ _':  # Run a test/example when run as a script:
    a = Fifo(  )
    a.append(10)
    a.append(20)
    print a.pop( )
    a.append(5)
    print a.pop( )
    print a.pop ()

Discussion

Most likely, the best way to do a FIFO in Python is to use standard lists with append and pop(0) methods. Since lists are built-ins, they are usually far more efficient than this recipe, despite theoretical considerations of O(1) versus O(N) performance. If you want to try this, it’s easy:

class FifoList:
    def _ _init_ _(self):
        self.data = []
    def append(self, data):
        self.data.append(data)
    def pop(self):
        return self.data.pop(0)

A quirky variation that ensures O(1) performance can be built on top of a dictionary:

class FifoList: def _ _init_ _(self): self.data = {} self.nextin = 0 self.nextout = 0 def append(self, data): self.nextin += 1 self.data[self.nextin] ...