剑指offer：包含min函数的栈

题目描述


定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。


剑指offer给出的思路：
      我们可能想使用一个变量min来存放最小的元素。每次压入栈中一个元素的时候，如果新元素比这个变量min中保存的元素小，那么就将用新元素给min赋值，即更新min的值。但是，这样存在一个问题，那就是当当前最小的元素被弹出栈了，怎么得到栈中剩余元素的最小的元素呢？
      因此，可以借助一个辅助栈，用来存放每次栈操作时（包括入栈和出栈）栈中最小元素。


class Solution {
public:
    stack<int> st, minSt;//st表示存储元素的栈，minSt保存每次栈操作时，保存栈中最小元素
    void push(int value) {
        st.push(value);
        if (minSt.empty()){//如果栈minSt为空，将value入栈，value就是当前最小的元素
            minSt.push(value);
        }
        else {//如果栈minSt不为空，将value的值与minStrel栈的栈顶元素比较。因为minSt栈的栈顶元素此时为栈中所有元素的最小值
            if (value < minSt.top()){
                minSt.push(value);
            }
            else {
                minSt.push(minSt.top());
            }
        }
        return;
    }
    void pop() {//出栈时，需要对两个栈st和minSt同时操作
        if (!st.empty()) {
            st.pop();
            minSt.pop();
        }
        return;
    }
    int top() {
        if (!st.empty()){
            return st.top();
        }
        return 0;
    }
    int min() {
        if (!minSt.empty()) {
            return minSt.top();
        }
        return 0;
    }
};