Chapter 3 Stacks and Queues - 3.2
problem 3.2: How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

At first, I thought it was impossible to impement such a stack. However, when I turned to the answer page, I found that I ignored the most important property of stacks, FILO (First In Last Out). Each element in a stack can keep properties of all elements beneath it, for all elements below won't be changed before the element is removed. It means that we can record the minimum value of all elements in the element above them. When an element is at the top of the stack, the minimum value it keeps is the minimum value of all elements in the stack.
MAXIMUM_VALUE = 1e7class node_with_min: def __init__(self, value = None): self.pre = None self.value = value # Each node keeps record of minimum value in the stack, # when it is at the top of the stack self.min = Noneclass stack_with_min: def __init__(self): self.bottom = node_with_min(MAXIMUM_VALUE) self.bottom.min = MAXIMUM_VALUE self.top = self.bottom self.length = 0 def push(self, value): min_val = min([value, self.top.min]) new_node = node_with_min(value) new_node.min = min_val new_node.pre = self.top self.top = new_node self.length = self.length + 1 def pop(self): if self.length <= 0: return False to_delete = self.top to_return = self.top.value self.top = self.top.pre del to_delete self.length = self.length - 1 return to_return def min_element(self): if self.length <= 0: return False return self.top.min# Test casesif __name__ == "__main__": stack = stack_with_min() stack.push(0) print "push 0, min = ", stack.min_element() stack.push(1) print "push 1, min = ", stack.min_element() stack.push(2) print "push 2, min = ", stack.min_element() stack.push(-1) print "push -1, min = ", stack.min_element() stack.push(-2) print "push -2, min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element() print "pop,", stack.pop(), "min = ", stack.min_element()
The lesson is: you can achieve quite high performance if you sacrifice space. If you cannot achieve performance that is high enougth, you didn't sacrifice enough space.