--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch4ex1.py	Mon Dec 31 18:58:21 2012 -0600
@@ -0,0 +1,82 @@
+"""Section 4.2, exercise 1 of Allen Downey's Think Complexity book.
+
+"Write an implementation of a FIFO using either a doubly-linked list or
+a circular buffer."
+
+"""
+
+class Node(object):
+
+    def __init__(self, data):
+        self.prev = self.next = None
+        self.data = data
+
+class Fifo(object):
+
+    def __init__(self):
+        self.first = None
+        self.last = None
+
+    def append(self, val):
+        """Append a value onto the back of the queue."""
+
+        node = Node(val)
+
+        if self.last:
+            self.last.next = node
+            node.prev = self.last
+
+        self.last = node
+
+        if not self.first:
+            self.first = node
+
+    def pop(self):
+        """Remove and return the value at the front of the queue.
+
+        Raises an IndexError if the queue is empty.
+        """
+        if not self.first:
+            raise IndexError
+
+        node = self.first
+        self.first = node.next
+        node.prev = node.next = None
+
+        if self.last is node:
+            self.last = None
+
+        return node.data
+
+    def empty(self):
+        """Returns True if the queue is empty and False otherwise."""
+        return self.first is None and self.last is None
+
+
+if __name__ == '__main__':
+    import random
+    values = range(100)
+    random.shuffle(values)
+
+    fifo = Fifo()
+    assert fifo.empty()
+
+    for v in values:
+        fifo.append(v)
+
+    got = []
+    while not fifo.empty():
+        got.append(fifo.pop())
+
+    assert got == values
+
+    fifo.append(42)
+    assert fifo.pop() == 42
+    assert fifo.empty()
+
+    try:
+        fifo.pop()
+    except IndexError:
+        pass
+    else:
+        assert False