Site icon Dipin Krishna

Python: Stack with Push, Pop and seek Minimum Value with O(1)

python

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.

Exit mobile version