Implementing additional function to stack data structure

Question

How would i design a stack which in addition to push() and pop() ,also has a function min which returns the minimums element ? min() must operate in big O(1) time

Answer 1

You need an additional stack of minimums. In push, if the new element is less than or equal to the top of the min-stack, push it there too. In pop, if the popped element is equal to the top of the minstack, pop it from there too.

Answer 2

As pointed out by others, you need to create another stack of minimums. Technically this would still be O(1), but its space would be multiplied by a constant factor of two. This is a python implementation using lists:

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