This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).
Complexity:
Complexity:
In [1]:
%run ../stack/stack.py
In [2]:
class StackWithCapacity(Stack):
def __init__(self, top=None, capacity=10):
self.capacity = capacity
self.num_items = 0
super(StackWithCapacity, self).__init__(top)
def push(self, data):
if self.num_items < self.capacity:
super(StackWithCapacity, self).push(data)
self.num_items += 1
else:
raise Exception('Stack full')
def pop(self):
data = super(StackWithCapacity, self).pop()
self.num_items -= 1
return data
def is_full(self):
return self.num_items == self.capacity
class SetOfStacks(object):
def __init__(self, capacity):
self.capacity = capacity
self.stacks = []
self.last_stack = None
def push(self, data):
if self.last_stack is None or self.last_stack.is_full():
self.last_stack = StackWithCapacity(None, self.capacity)
self.stacks.append(self.last_stack)
self.last_stack.push(data)
def pop(self):
if self.last_stack is None:
return
elif self.last_stack.top.next is None:
data = self.last_stack.pop()
self.stacks.pop()
num_stacks = len(self.stacks)
if num_stacks == 0:
self.last_stack = None
else:
self.last_stack = self.stacks[num_stacks-1]
else:
data = self.last_stack.pop()
return data
In [3]:
%%writefile test_set_of_stacks.py
from nose.tools import assert_equal
class TestSetOfStacks(object):
def test_set_of_stacks(self):
print('Test: Push on an empty stack')
capacity = 2
stacks = SetOfStacks(capacity)
stacks.push(3)
print('Test: Push on a non-empty stack')
stacks.push(5)
print('Test: Push on a capacity stack to create a new one')
stacks.push('a')
print('Test: Pop on a one element stack to destroy it')
assert_equal(stacks.pop(), 'a')
print('Test: Pop general case')
assert_equal(stacks.pop(), 5)
assert_equal(stacks.pop(), 3)
print('Test: Pop on no elements')
assert_equal(stacks.pop(), None)
print('Success: test_set_of_stacks')
def main():
test = TestSetOfStacks()
test.test_set_of_stacks()
if __name__ == '__main__':
main()
In [4]:
%run -i test_set_of_stacks.py