包含min函数的栈

LeetCode 155. Min Stack 设计一个栈，支持如下操作，这些操作的算法复杂度需要是常数级，O(1) 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.getMin() : 返回栈内最小元素

class MinStack{
public:
    MinStack(){
    }//构造函数
    void push(int x){
    }//将元素x压入栈
    void pop(){
    }//将栈顶元素弹出
    int top(){
    }//返回栈顶元素
    int getMin(){
    }//返回站内最小元素
}

数据使用普通的栈data_stack存储，另外设置一个变量MIN，记录入栈过程中遇到的最小值，各项操作时有如下算法: 1.push(x) : 将元素x压入栈中，若x小于MIN，则更新变量MIN = x。 2.pop() : 弹出(移除)data_stack栈顶元素。 3.top() : 返回data_stack栈顶元素。 4.getMin() : 返回变量MIN。

分析

1.个变量MIN无法完成记录栈中所有状态的最小值，例如当栈进行pop操作的时候，数据栈更新了，也需要更新MIN变量的，但此时并未记录栈中第二小的元素，故没办法更新MIN变量。 2.栈的每个状态，都需要有一个变量记录最小值，每个状态即指无论对栈进行了push或pop操作， 该时刻的栈的最小值是被记录的。 3.在push或pop时，不能对数据进行排序，因为排序的复杂度不是O(1)。

算法设计

设置两个栈，数据栈data_stack与最小值栈min_stack，这两个栈对于添加元素push与弹出栈顶元素pop都是同步进行的: 1.push(x) : 将元素x直接压入数据栈data_stack中，若x小于最小值栈栈顶，则将x压入最小值栈中， 否则将最小值栈栈顶压入最小值栈。 2.pop() : 同时弹出(移除)数据栈栈顶与最小值栈顶元素。 3.top() : 返回数据栈data_stack栈顶元素。 4.getMin() : 返回最小值栈min_stack栈顶元素

class MinStack{
public:
    MinStack(){
}
    void push(int x){
        _data.push(x);//将数据压入数据栈
         if(_min.empty()){
             _min.push(x);
         }
        else{
            if(x>_min.top()){
                x = _min.top();
            }
            _min.push(x);
        }
}//比较当前数据与最小值栈栈顶数据大小，选择较小的压入最小值栈
void pop(){
    _data.pop();
    _min.pop();
}
int top(){
    return _data.top();
}
int getMin(){
    return _min.top();
}
private:
    std::stack<int> _data;//
    std::stack<int> _min;//
};