Step 8 of 8
Challenge: a MinStack<T>
A classic interview question, now generic. Your turn: write template <typename T> class MinStack where every operation is O(1), including finding the minimum:
void push(const T& v)void pop()(assume non-empty)const T& top() constconst T& min() const: the smallest element currently in the stackbool empty() const
Hint for the O(1) min: alongside each value, remember what the minimum was at that point. Or keep a second stack of minimums.