17.15 Implementing a First-In First-Out Container

Credit: Sébastien Keim

17.15.1 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).

17.15.2 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(0)
    a.append(5)
    print a.pop(0)
    print a.pop(0)

17.15.3 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] = data
    def pop(self):
        self.nextout += 1
        result = self.data[self.nextout]
        del self.data[self.nextout]
        return result

I developed this recipe after I read an academic paper that said that double-linked lists were the natural way to create this kind of container (in contrast with stacks). I convinced myself that it was possible and quite natural to create a FIFO container with single-linked lists, instead. It suffices to have two references to first and last in the Fifo class itself. The class in the recipe's solution shows one way to build a single-linked list in Python via pairs that reference the actual data (also known as the payload) as their first item and use the second item to refer to another such pair (None being used as a null pointer here).

The append method builds such a pair (actually a two-item list) and threads it onto the list, altering the first and last attributes of self appropriately. The popmethod unthreads the node at the head of the list in a similar but mirrored way.