Last Updated: August 01, 2023
·
745
· lukasz-madon

MinStack

Data structure that behaves just like a stack in terms of push and pop, but also return minimum in constant time)

class MinStack():
    def __init__(self):
        self.stack = []
        self.currentMin = None

    def push(self, elem):
        if not self.stack or elem <= self.currentMin:
            self.stack.append(self.currentMin)
            self.currentMin = elem            
        self.stack.append(elem)

    def pop(self):
        if not self.stack:
            return None  # or throw
        elem = self.stack.pop()
        if elem == self.currentMin:
            self.currentMin = self.stack.pop()
        return elem

a = MinStack()
a.push(1)
a.push(2)
a.push(3)
a.push(-2)
print a.currentMin
a.pop()
print a.currentMin
a.pop()
print a.currentMin
a.pop()
print a.currentMin
a.pop()
print a.currentMin
a.pop()
print a.currentMin
a.pop()