C++的STL栈实现获取栈中最小元素的成员

实现一个获取栈中最小数据成员的函数，该栈支持如下操作：

1.push(x) : 将元素x压入栈中

2.pop() : 弹出(移除)栈顶元素

3.top() : 返回栈顶元素

4.getMin() : 返回栈内最小元素

要求时间复杂度为O(1)

这里关键是如何获取最小值，栈中的元素不断增加，且要达到O（1）常数级的时间复杂度，即创建好的栈进行排序，返回最小值是不可行的。

这里只有在创建过程中将栈中的最小值获取到，此时一个可行的办法为：

维护一个最小栈，保持栈顶元素为所有元素的最小值，且大小与原本数据栈保持一致。

这样即使有原本数据的删除添加，最小栈同样跟随数据删除添加即可。

方法一（一个栈）：

数据结构实现如下:

void push(int x) {
   data_stack.push(x);
   /*当最小栈中的元素不为空的时候，和栈顶元素进行大小比较，判断是否要入栈*/
   if (!min_stack.empty()) {
       if (min_stack.top() > x) {
           min_stack.push(x);
       }
       else {
           min_stack.push(min_stack.top());
       }
   }
   /*为空的时候即可入栈*/
   else {
       min_stack.push(x);
   }
}
/*此时最小栈的栈顶即为数据栈中的最小元素*/
int get_min(){
    return min_stack.top();
}      

方法二（两个栈）：

class MinStack {
    stack<int> S;
    int min=2147483647;
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    //push操作
    void push(int x) {
        if (x <= min) { //当遇到小于等于最小值的数值，将上一个最小值也push到栈中
            S.push(min);
            min = x;
        }
        S.push(x);
    }
    
    void pop() {
        if (S.top() == min) { //pop的时候发现pop的时最小值，那么pop两次，同时变更最小值
            S.pop();
            min = S.top();
            S.pop();
        } else {
            S.pop();
        }
    }
    
    int top() {
        return S.top();
    }
    
    int getMin() {
        return min;
    }
};      

#include <stack>
#include <iostream>
#include <algorithm>

using namespace std;

class My_stack{
    private:
    stack<int> data_stack,min_stack;

    public:
    void push(int x) {
        data_stack.push(x);

        if (!min_stack.empty()) {
            if (min_stack.top() > x) {
                min_stack.push(x);
            }
            else {
                min_stack.push(min_stack.top());
            }
        }
        else {
            min_stack.push(x);
        }
    }

    void pop() {
        min_stack.pop();
        data_stack.pop();
    }

    int top() {
        return data_stack.top();
    }

    int get_min(){
        return min_stack.top();
    }
};

int main(){
    My_stack s;
    int tmp;
    cout << "construct the stack " << endl;
    while(cin >> tmp) {
        s.push(tmp);
    }

    cout << "min is " << s.get_min() << endl;
    s.pop();
    cout << "after pop " << s.top() << endl;
    s.push(-4);
    cout << "after push ,the top and min is " << s.top() << " " << s.get_min() << endl;
    return 0;
}      

construct the stack 
2 -1 -3 2 0 4
d
min is -3
after pop 0
after push -4,the top and min is -4 -4