Merge remote-tracking branch 'upstream/data_structures' into undirected_adjacency_matrix

skirkpatrick · skirkpatrick · commit 37c3070de943 · 2013-04-01T14:22:37.000-07:00
Conflicts:
	algorithms/tests/test_data_structures.py
diff --git a/algorithms/data_structures/stack.py b/algorithms/data_structures/stack.py
@@ -0,0 +1,29 @@
+"""
+Stacks are cool
+"""
+
+class EmptyStackError(Exception):
+    pass
+
+class Element(object):
+    def __init__(self, value, next):
+        self.value = value
+        self.next = next
+
+
+class Stack(object):
+    def __init__(self):
+        self.head = None
+
+    def push(self, element):
+        self.head = Element(element, self.head)
+
+    def pop(self):
+        if self.empty():
+            raise EmptyStackError
+        result = self.head.value
+        self.head = self.head.next
+        return result
+
+    def empty(self):
+        return self.head == None
diff --git a/algorithms/tests/test_data_structures.py b/algorithms/tests/test_data_structures.py
@@ -1,6 +1,6 @@
 """ Unit Tests for data structures """
 import unittest
-from ..data_structures import undirected_adjacency_matrix
+from ..data_structures import undirected_adjacency_matrix, Stack, EmptyStackError
 
 
 class TestUndirectedAdjacencyMatrix(unittest.TestCase):
@@ -73,3 +73,26 @@ def test_undirected_adjacency_matrix(self):
         for i in range(0, 20, 2):
             self.graph.removeVertex(i)
         self.assertEqual(self.expected[5], self.graph.edge)
+
+
+class TestStack(unittest.TestCase):
+    """
+    Tests the methods of the Stack data structure.
+    """
+
+    def setUp(self):
+        self.input = range(5)
+        self.stack = Stack()
+        self.reverse = [4, 3, 2, 1, 0]
+
+    def test_stack(self):
+        for i in self.input:
+            self.stack.push(i)
+
+        result = []
+
+        while not self.stack.empty():
+            result.append(self.stack.pop())
+
+        self.assertEqual(self.reverse, result)
+        self.assertRaises(EmptyStackError, self.stack.pop)
