MinStack

Estrutura de dados que se comporta como uma pilha em termos de push e pop, mas também retorna mínimo em tempo constante)

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()