定义栈并得到最小元素

---

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度为O(1).保证测试中不会当栈为空的时候，对栈调用pop() min() top()方法。

解题思路

可以通过两个栈来实现栈的数据结构。一个栈Data存放数据，另一个栈Min存放最小值。

• 入栈：直接将数据压入数据栈Data中。若最小栈Min为空直接将数据压入。若Min栈不为空将当前值与栈顶部元素比较，若较小则压入Min栈；否则不做处理。
• 出栈：若数据栈Data和最小栈Min的栈顶元素相同，则弹出Min栈顶元素，同时弹出数据栈Data栈顶元素；否则弹出数据栈Data栈顶元素。
• 栈顶元素：直接用数据栈Data的栈顶元素
• 最小元素：直接调用最小栈Min的栈顶元素

代码

class Solution
{
public:
    void push(int value)
    {
        Data.push(value);
        if (Min.empty())
            Min.push(value);
        if (Min.top() > value)
            Min.push(value);
    }
    void pop()
    {
        if (!Data.empty()) //栈不为空
        {
            if (Data.top() == Min.top())
                Min.pop();
            Data.pop();
        }
    }
    int top()
    {
        if (!Data.empty())
            return Data.top();
    }
    int min()
    {
        if (!Data.empty())
            return Min.top();
    }
private:
    stack<int> Data;
    stack<int> Min;
};

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_20.html