设计一个可以获取最小值功能的栈

矫情吗；* 2022-07-24 08:26 117阅读 0赞

## 设计一个有getMin功能的栈 – C++实现 ##

【题目】：  
　　实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。  
【要求】：  
　　1、pop、push、getMin操作的时间复杂度都是O(1)。  
　　2、设计的栈类型可以使用现成的栈结构。

--------------------

## 解题设计 ##

使用两个栈，一个栈保存当前栈中元素(stackData)，另一个保存每次入栈的最小值(stackMin)。

--------------------

具体解题算法C++代码：

class MyStack
    {
    private:
        stack<int>* stackData; //数据栈
        stack<int>* stackMin;  //最小栈
    public:
        MyStack()
        {
            stackData = new stack<int>;
            stackMin = new stack<int>;
        }
        ~MyStack()
        {
            delete stackData;
            delete stackMin;
        }
        //压栈
        bool push(int newNum)
        {
            //最小栈若为空，压入新元素，否则比较新元素和最小值大小，小于等于最小值时压栈
            if (stackMin->empty()) 
            {
                stackMin->push(newNum);
            }    
            else if (newNum <= getMin())
            {
                stackMin->push(newNum);
            }
    
            stackData->push(newNum);
            return true;
        }
        //出栈，返回stackData栈顶元素
        int pop()
        {
            if (stackData->empty())
                throw runtime_error ("stackData is empty");
    
            int value = stackData->top();
            stackData->pop();
            //数据栈中元素删除时，若此数据存在于最小栈中，最小栈栈顶元素出栈
            if (value == getMin())
            {
                stackMin->pop();
            }
            return value;
        }
        //获取栈中最小值
        int getMin()
        {
            if (stackMin->empty())
                throw runtime_error("stackMin is empty");
            return stackMin->top();
        }
    };

--------------------

## 测试用例 ##

#include <iostream>
    #include <stack>
    #include <stdexcept>
    #include <exception>
    
    using namespace std;
    
    //上述算法代码
    
    int main()
    {
        MyStack s;
        s.push(7);
        s.push(6);
        s.push(5);
        s.push(4);
        s.push(5);
        s.push(3);
        s.push(2);
        s.push(13);
        s.push(1);
        cout << "min: " << s.getMin();
        cout << endl;
    
        cout << "after pop:" << endl;
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        cout << "min: " << s.getMin();
        cout << endl;
    
        system("pause");
    }

**运行结果：**

min: 1
    after pop:
    min: 5
    请按任意键继续. . .