I have written a stack in Python that is required to push, pop and return the minimum of the stack in \$O(1)\$ time.
#!python3
class Stack():
def __init__(self):
self.items = []
self.min = None
def push(self, item):
self.items.append(item)
self.minimum()
def pop(self):
if self.isEmpty():
raise ValueError('Empty stack')
else:
return self.items.pop()
def minimum(self):
if self.min is None:
self.min = self.peek()
else:
if self.peek() < self.min:
self.min = self.peek()
def getMinimum(self):
return self.min
def peek(self):
try:
return self.items[-1]
except IndexError as e:
print(e)
def size(self):
return len(self.items)
def isEmpty(self):
return self.size() == 0
stack = Stack()
nums = [6,4,8,9,1,5,2,3]
for i in nums:
stack.push(i)
print(stack.getMinimum())
What I have tried to do is, compare the current minimum with each new addition to the stack so that the
self.min
attribute constantly updates.
Eventually, to get the minimum, I simply call the
self.getMinimum()
function to return the minimum. My question is, does this actually occur in \$O(1)\$ time?