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

  • A+
所属分类: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压入时稍费空间,但是弹出操作稍省时间。

百分购

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: