Implementazione di una funzione aggiuntiva per impilare la struttura dei dati

Hai bisogno di una pila aggiuntiva di minimi. In push , se il nuovo elemento è minore o uguale alla cima del min-stack, spingilo anche lì. In pop , se l'elemento popped è uguale alla parte superiore del minstack, fai un salto anche da lì.

Come sottolineato da altri, è necessario creare un altro gruppo di minimi. Tecnicamente questo sarebbe ancora O (1), ma il suo spazio sarebbe moltiplicato per un fattore costante di due. Questa è un'implementazione python usando liste:

class Empty(Exception):
    pass

class MinStack(object):

    def __init__(self):
        self._data = []
        self._min_stack = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0

    def push(self, x):
        if self.is_empty():
            self._min_stack.append(x)
        elif x <= self._min_stack[0]:
            self._min_stack.insert(0,x)
        self._data.append(x)

    def pop(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        if self._min_stack[0] == self._data[-1]:
            del self._min_stack[0]
        return self._data.pop() 

    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data[-1]

    def getMin(self):
        return self._min_stack[0]

if __name__ == '__main__':
    obj = MinStack()
    for i in [0,1,0]:
        obj.push(i)
    obj.getMin()
    obj.pop()
    obj.getMin()