Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. This problem is included in CC150 (See 3.2 in Chapter 3 ). Further improvement could be save the counter of duplicates (the current version push some duplicates into two stacks).