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
attribute constantly updates.
Eventually, to get the minimum, I simply call the
function to return the minimum. My question is, does this actually occur in \$O(1)\$ time?