（十四）剑指offer之栈的压入弹出序列及包含min函数的栈

1、题目描述：

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

class Solution {
public:
    void push(int value) {
        s_data.push(value);
        if(s_min_data.size()==0 || value < s_min_data.top())
            s_min_data.push(value);
        else
            s_min_data.push(s_min_data.top());
    }
    void pop() {
        if(s_data.size() > 0 && s_min_data.size() > 0){
            s_data.pop();
            s_min_data.pop();
        }
    }
    int top() {
        return s_data.top();
    }
    int min() {
        return s_min_data.top();
    }
private:
    stack<int> s_data;
    stack<int> s_min_data;
};

2、题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
（注意：这两个序列的长度是相等的）

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        bool Ispossible = false;
        if(!pushV.empty() && !popV.empty()){
            stack<int> s_data;
            auto pushNext = pushV.begin();
            auto popNext = popV.begin();
            while(popNext != popV.end()){
                while(s_data.empty() || s_data.top() != *popNext){
                    if(pushNext == pushV.end()) break;
                    s_data.push(*pushNext);
                    pushNext++;
                }
                if(s_data.top() != *popNext) break;
                s_data.pop();
                popNext++;
            }
            if(s_data.empty() && popNext == popV.end())
                Ispossible = true;
        }
        return Ispossible;
    }
};

如有建议或其他问题，可随时给我们留言。或者到以下链接：

https://github.com/gaobaoru/code_day

Star/Fork/Push 您的代码，开源仓库需要您的贡献。

请查看Coding 题目网址和收藏Accepted代码仓库，进行coding！！！