剑指offer*30包含min 函数的栈

题目

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

答案

class Solution {
private:
    stack<int> st;
    stack<int> smin;
public:
    void push(int value) {
        st.push(value);
        if(smin.empty())
            smin.push(value);
        if(smin.top()>value)
            smin.push(value);
        else
            smin.push(smin.top());
    }
    void pop() {
        smin.pop();
        st.pop();
    }
    int top() {
        return st.top();
    }
    int min() {
        return smin.top();
    }
};

思路

使用一个辅助栈，当往正常栈push元素时，如果辅助栈为空，就往辅助栈push元素，如果辅助栈的栈顶比当前要push的元素大，就往辅助栈push这个元素，如果辅助栈栈顶比push的元素小，就再push 栈顶的最小元素。