Credit: Sébastien Keim
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).
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 ()
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
pop
method unthreads the node at the head of the
list in a similar but mirrored way.