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

• JollyJoker: I assume you want the push and pop functions to remain O(1)?

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