一.题意整理

定义栈的数据结构,栈是一个先进后出的数据结构,下面将实现如下的函数功能:

push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
例如:栈:2 5 6 23 17
分别实现:
push(9)后栈序列:2 5 6 23 17 9 
pop()后栈序列:2 5 6 23 
top()返回值是栈顶元素:17
min()返回栈中的最小元素:2

二.思路整理

首先会给大家介绍c++中的STL,STL是标准模板库(Standard Template Library)是c++内置实现的函数模板,其中包括了栈的实现。

stack<type>函数名字 实现对栈的定义
empty() 堆栈为空则返回真
pop() 移除栈顶元素
push() 在栈顶增加元素
size() 返回栈中元素数目
top() 返回栈顶元素

然后我们回到本题目,要对于入栈、出栈、栈顶在STL中都已经实现好了,但是对于返回最小值的操作却没有实现,可能有人说遍历一遍不就可以了,但是在STL中stack是不支持遍历,那么对于最小值我们该如何实现呢?我们可以利用一个辅助栈来实现对最小值的维护。对于每一次入栈的元素我们对其进行判断,要是入栈元素小于当前辅助栈的栈顶,那么目前最小值就是当前入栈元素;若入栈元素大于当前辅助栈的栈顶,那么很显然当前元素的加入不影响最小值,那么就将辅助栈的栈顶入栈,来维持最小值。那么在每次出栈的时候,由于辅助站都是维护栈顶元素的最小值,所以在出栈的时候辅助栈和主栈都要同时出栈。 alt

三.代码实现

class Solution {
public:
    stack<int>st,mi;
    //利用STL中的定义两个栈
    //st是辅助栈
    void push(int value) {
        st.push(value);
        if(!mi.size()){
            mi.push(value);
        } else {
            //辅助站的为维护
            if(value<=mi.top()){
                mi.push(value);
            } else {
                mi.push(mi.top());
            }
        }
    }
    void pop() {
        //由于辅助站的维护 两个栈都必须同时出栈
        st.pop();
        mi.pop();
    }
    int top() {
        return st.top();
    }
    int min() {
        //返回辅助栈的最小元素
        return mi.top();
    }
};