设计一个有getMin功能的栈(c++实现)

设计一个有getMin功能的栈

题目

实现一个特殊的栈，在实现栈的基础功能的基础上，再实现返回栈中最小元素的操作。

要求

• pop、push、getMin操作的时间复杂度都是O(1)。
• 设计的栈类型可以使用现场的栈结构。

解答

在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈相同，这个栈记为stackData；另一个栈用来保存每一步的最小值，这个栈记为stackMin。实现方式有如下两种:

第一种设计方案

• 压入数据规则

假设当前数据为newNum,先将其压入stackData。然后判断stackMin是否为空：

1. 如果为空，则newNum也压入stackMin。
2. 如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小:
3. 如果newNum更小或两者相等，则newNum也压入stackMin;
4. 如果stackMin中栈顶元素小，则stackMin不压入任何内容。

• 弹出数据规则

先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。
当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素;返回value。

• 查询当前栈中的最小值操作

由上文的压入数据规则可知，stackMin始终记录着stackData中的最小值，所以，stackMin的栈顶元素始终是当前stackData中的最小值。

方案一实现代码如下：

#include <iostream>
#include <stack>
using namespace std;

class MyStack1 {
    public:
        void push(int const newNum) {
            if (stackMin.empty()) {
                stackMin.push(newNum);
            }else if (newNum <= getmin()) {
                stackMin.push(newNum);
            }
            stackData.push(newNum);
        }
        int pop() {
            if (stackData.empty()) {
                throw "Your stack is empty.";
            }
            int value = stackData.top();
            stackData.pop();
            if (value == getmin()) {
                stackMin.pop();
            }
            return value;
        }
        int getmin() {
            if (stackMin.empty()) {
                throw "Your stack is empty.";
            }
            return stackMin.top();
        }
    private:
        stack<int> stackData;
        stack<int> stackMin;
};

int main() {
    MyStack1 mStack1;
    mStack1.push(3);
    mStack1.push(4);
    cout << mStack1.getmin() << endl;
    mStack1.push(5);
    cout << mStack1.getmin() << endl;
    mStack1.push(1);
    cout << mStack1.getmin() << endl;
    mStack1.push(2);
    cout << mStack1.getmin() << endl;
    mStack1.push(1);
    cout << mStack1.getmin() << endl;
    return 0;
}

第二种设计方案

• 压入数据规则

假设当前数据为newNum,先将其压入stackData。然后判断stackMin是否为空。
如果为空，则newNum也压入stackMin;如果不为空，则比较newNum和stackMin的栈顶元素哪一个更小:
如果newNum更小或者两者相等，则newNum也压入stackMin；如果stackMin中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。

• 弹出数据规则

在stackData中弹出数据，弹出的数据标记为value;弹出stackMin中的栈顶；返回value。

• 查询当前栈中的最小值操作

由上文的压入数据规则可知，stackMin始终记录着stackData中的最小值，所以，stackMin的栈顶元素始终是当前stackData中的最小值。

方案二实现代码如下：

#include <iostream>
#include <stack>
using namespace std;

class MyStack2 {
    public:
        void push(int const newNum) {
            if (stackMin.empty()) {
                stackMin.push(newNum);
            }else if (newNum <= getmin()) {
                stackMin.push(newNum);
            }else {
                int newMin = stackMin.top();
                stackMin.push(newMin);
            }
            stackData.push(newNum);
        }
        int pop() {
            if (stackData.empty()) {
                throw "Your stack is empty.";
            }
            int value = stackData.top();
            stackMin.pop();
            stackData.pop();
            return value;
        }
        int getmin() {
            if (stackMin.empty()) {
                throw "Your stack is empty.";
            }
            return stackMin.top();
        }
    private:
        stack<int> stackData;
        stack<int> stackMin;
};

int main() {
    MyStack2 mStack2;
    mStack2.push(3);
    mStack2.push(4);
    cout << mStack2.getmin() << endl;
    mStack2.push(5);
    cout << mStack2.getmin() << endl;
    mStack2.push(1);
    cout << mStack2.getmin() << endl;
    mStack2.push(2);
    cout << mStack2.getmin() << endl;
    mStack2.push(1);
    cout << mStack2.getmin() << endl;
    return 0;
}

总结

方案一和方案二都用stackMin栈报错这stackData每一步的最小值。共同点是所有操作的时间复杂度都是O(1)、空间复杂度都为O(n)。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。