cwdawg
Last Updated: February 25, 2016
·
483
· lukasz-madon
B2bc42f69510d6a1d2c9cde1c2214d24

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()
Say Thanks
Respond