Python implementation of stack to return minimum in O(1) time

Question

I have written a stack in Python that is required to push, pop and return the minimum of the stack in \$O(1)\$ time.

#!python3
class Stack():
    def __init__(self):
        self.items = []
        self.min = None

    def push(self, item):
        self.items.append(item)
        self.minimum()

    def pop(self):
        if self.isEmpty():
            raise ValueError('Empty stack')
        else:
            return self.items.pop()

    def minimum(self):
        if self.min is None:
            self.min = self.peek()
        else:
            if self.peek() < self.min:
                self.min = self.peek()

    def getMinimum(self):
        return self.min

    def peek(self):
        try:
            return self.items[-1]
        except IndexError as e:
            print(e)

    def size(self):
        return len(self.items)

    def isEmpty(self):
        return self.size() == 0

stack = Stack()

nums = [6,4,8,9,1,5,2,3]
for i in nums:
    stack.push(i)

print(stack.getMinimum())

What I have tried to do is, compare the current minimum with each new addition to the stack so that the

self.min

attribute constantly updates.

Eventually, to get the minimum, I simply call the

self.getMinimum()

function to return the minimum. My question is, does this actually occur in \$O(1)\$ time?

Answer 1

You can correctly implement the stack with minimum query by maintaining a second array that holds current minimum on its top. When you push the very first element, you append it to both the arrays. Next, when you push the subsequent element \$e\$, you append it to the actual stack array as is, but you push \$\min \{ e, e' \}\$ to the minimum stack, where \$e'\$ is the top element of the minimum stack. Popping is trivial: just pop both the actual element array and the minimum array. All in all, it might look like this:

class Stack():

    def __init__(self):
        self.element_stack = []
        self.min_element_stack = []

    def push(self, item):
        if self.size() == 0:
            self.min_element_stack.append(item)
        else:
            self.min_element_stack.append(min(self.min_element_stack[self.size() - 1], item))
        self.element_stack.append(item)

    def pop(self):
        if self.is_empty():
            raise ValueError('Empty stack')
        self.min_element_stack.pop()
        return self.element_stack.pop()

    def minimum(self):
        if self.is_empty():
            raise ValueError('Empty stack')
        return self.min_element_stack[self.size() - 1]

    def is_empty(self):
        return self.size() == 0

    def size(self):
        return len(self.element_stack)


def main():
    stack = Stack()
    stack.push(3)
    print(stack.minimum())
    stack.push(5)
    print(stack.minimum())
    stack.push(1)
    print(stack.minimum())
    stack.pop()
    print(stack.minimum())

if __name__ == "__main__":
    main()

Hope that helps.

Answer 2

The minimum gets updated after a push but not after a pop, causing getMinimum to return the wrong value:

>>> stack = Stack()
>>> stack.push(2)
>>> stack.push(1)
>>> stack.getMinimum()
1 # correct
>>> stack.pop()
1
>>> stack.getMinimum()
1 # wrong: the only item in the stack now is the number 2

Answer 3

• In Python 3, a class is typically not declared with parentheses (Python 2 required deriving classes from object: class A(object), however this isn't the case in Python 3).

• Shebangs should be #!/usr/bin/env python3 for Python 3.

• If I am not mistaken, this is in fact \$ O(1) \$, since it is not influenced by the size of the stack.