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

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


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?

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.

• Question not strictly related to the implementation. What does the if name == "main" do? I have seen this before, and I assume it has something to do with testing? – Zaid Humayun Jul 7 '17 at 4:43
• – coderodde Jul 7 '17 at 5:05

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

• 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.