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.