class AbstractStack:
def __init__(self):
self.top = 0
def isEmpty(self):
return self.top == 0
def __len__(self):
return self.top
def __str__(self):
result = '------\n'
for element in self:
result += str(element) + '\n'
return result[:-1] + '\n------'
class ArrayStack(AbstractStack):
def __init__(self, size=10):
"""
Initialize python List with size of 10 or user given input.
Python List type is a dynamic array, so we have to restrict its
dynamic nature to make it work like a static array.
"""
AbstractStack.__init__(self)
self.array = [None] * size
def push(self, value):
if self.top == len(self.array):
self.expand()
self.array[self.top] = value
self.top += 1
def pop(self):
if self.isEmpty():
raise IndexError("stack is empty")
value = self.array[self.top - 1]
self.array[self.top - 1] = None
self.top -= 1
return value
def peek(self):
if self.isEmpty():
raise IndexError("stack is empty")
return self.array[self.top]
def expand(self):
"""
expands size of the array.
Time Complexity: O(n)
"""
newArray = [None] * len(self.array) * 2 # double the size of the array
for i, element in enumerate(self.array):
newArray[i] = element
self.array = newArray
def __iter__(self):
probe = self.top - 1
while True:
if probe < 0:
raise StopIteration
yield self.array[probe]
probe -= 1
class StackNode(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedListStack(AbstractStack):
def __init__(self):
AbstractStack.__init__(self)
self.head = None
def push(self, value):
node = StackNode(value)
node.next = self.head
self.head = node
self.top += 1
def pop(self):
if self.isEmpty():
raise IndexError("stack is empty")
value = self.head.value
self.head = self.head.next
self.top -= 1
return value
def peek(self):
if self.isEmpty():
raise IndexError("stack is empty")
return self.head.value
def __iter__(self):
probe = self.head
while True:
if probe is None:
raise StopIteration
yield probe.value
probe = probe.next
# Stack Abstract Data Type (ADT)
# Stack() creates a new stack that is empty.
# It needs no parameters and returns an empty stack.
# push(item) adds a new item to the top of the stack.
# It needs the item and returns nothing.
# pop() removes the top item from the stack.
# It needs no parameters and returns the item. The stack is modified.
# peek() returns the top item from the stack but does not remove it.
# It needs no parameters. The stack is not modified.
# isEmpty() tests to see whether the stack is empty.
# It needs no parameters and returns a boolean value.
# size() returns the number of items on the stack.
# It needs no parameters and returns an integer.