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