Pyhton 3 code to implement a stack with push, pop and seekMin function with time complexity of O(1)
class Stack: def __init__(self): self.items = [] self.minList = [] self.min = None def push(self, item): print("Push: ", item) self.items.append(item) if not self.min: self.min = item else: if item <= self.min: self.minList.append(self.min) self.min = item self.printAll() def pop(self): if self.items: item = self.items.pop() if item == self.min: self.min = self.minList.pop() if self.minList else None print("Pop: ", item) self.printAll() return item print("Pop: ", None) self.printAll() return None def seekMin(self): print("Min: ", self.min) return self.min def printAll(self): print('Items: ' , self.items) print('Min List: ' , self.minList) print('Min: ' , self.min) print() stack = Stack() stack.push(5) stack.push(3) stack.pop() stack.push(2) stack.push(2) stack.push(4) stack.push(7) stack.push(3) stack.pop() stack.push(1) stack.pop() stack.pop() stack.pop() stack.seekMin()
dipin$ python3 2.py Push: 5 Items: [5] Min List: [] Min: 5 Push: 3 Items: [5, 3] Min List: [5] Min: 3 Pop: 3 Items: [5] Min List: [] Min: 5 Push: 2 Items: [5, 2] Min List: [5] Min: 2 Push: 2 Items: [5, 2, 2] Min List: [5, 2] Min: 2 Push: 4 Items: [5, 2, 2, 4] Min List: [5, 2] Min: 2 Push: 7 Items: [5, 2, 2, 4, 7] Min List: [5, 2] Min: 2 Push: 3 Items: [5, 2, 2, 4, 7, 3] Min List: [5, 2] Min: 2 Pop: 3 Items: [5, 2, 2, 4, 7] Min List: [5, 2] Min: 2 Push: 1 Items: [5, 2, 2, 4, 7, 1] Min List: [5, 2, 2] Min: 1 Pop: 1 Items: [5, 2, 2, 4, 7] Min List: [5, 2] Min: 2 Pop: 7 Items: [5, 2, 2, 4] Min List: [5, 2] Min: 2 Pop: 4 Items: [5, 2, 2] Min List: [5, 2] Min: 2 Min: 2
Hope it helps.