Fifo mean "First In First Out". This is a kind of container, which only allow element insertion and removal and where the first element inserted is the first element removed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
class Fifo: def __init__(self): self.first=() def append(self,data): node = [data,()] if self.first: self.last = node else: self.first = node self.last = node def pop(self,n=-1): node = self.first self.first=node return node a=Fifo() a.append(10) a.append(20) print a.pop(0) print a.pop(0) a.append(5) print a.pop(0)
I would thanks Raymond Hettinger who has suggested many great improvements both to the code and the discussion part. He has also provided an interesting alternate implementation in the comment part.
Python offer the pop(0) method of standard list to implement fifo. Unfortunately lists pop(0) operation need to perform a copy of the whole content of the list, this is quite inefficient if you need to store a large set of data.
Linked lists data structure offer a way to do pop operation in constant time. In fact I did the previous code after I read an academic paper that said that double linked lists was the 'natural' way to do this kind of container (by contrast from stacks). I would convince myself that it was possible to create Fifo with single linked lists.
I've done some dirty benchmarking. Here some numerical results, this show the relative time to push N data in a fifo and pop them (this operation was repeated 10 time for each N)
(N, Python-lists, Simple-linked-list-fifo) (50, 0.01, 0.02) (100, 0.02, 0.03) (500, 0.12, 0.15) (1000, 0.3, 0.31) (5000 3.55, 1.69) (10000, 12.19, 3.48)
This results show that in single-linked-list pop and append duration don't depend on the numbers of items contained in the container. Builtin list solution seems to become inefficient when your fifo have to store more than 1000 items.
Note: Paul Moore code (in comment n°1) is very interesting and efficient, unfortunately this is not a fifo implementation but a stack implementation.