编写具有 getMin() 功能的栈

柔情只为你懂 2021-11-10 22:12 271阅读 0赞

#include <iostream>
    #include <stack>
    using namespace std;
    
    class MyStack1 {
    private:
        stack<int> stackData;
        stack<int> stackMin;
    public:
        MyStack1(){}
        ~MyStack1() {}
    
        int top() {
            if (stackData.empty()) {
                throw runtime_error("Your stack is empty.");
            }
            else {
                return stackData.top();
            }
        }
    
        void push(int newNum) {
            if (stackMin.empty()||newNum<=top()) {
                stackMin.push(newNum);
            }
            stackData.push(newNum);
        }
    
        int pop() {
            if (stackData.empty()) {
                throw runtime_error("Your stack is empty.");
            }
            int value = top();
            if (value == getMin()) {
                stackMin.pop();
            }
            stackData.pop();
            return value;
        }
    
        int getMin() {
            if (stackMin.empty()) {
                throw runtime_error("Your stackMin is empty.");
            }
            return stackMin.top();
        }
    };
    
    class MyStack2 {
    private:
        stack<int> stackData;
        stack<int> stackMin;
    public:
    
        int top() {
            if (stackData.empty()) {
                throw runtime_error("Your stack is empty.");
            }
            else {
                return stackData.top();
            }
        }
    
        void push(int newNum) {
            if (stackMin.empty() || newNum <= top()) {
                stackMin.push(newNum);
            }
            else {
                stackMin.push(getMin());
            }
            stackData.push(newNum);
        }
    
        int pop() {
            if (stackData.empty()) {
                throw runtime_error("Your stack is empty.");
            }
            stackMin.pop();
            int value = top();
            stackData.pop();
            return value;
        }
    
        int getMin() {
            if (stackMin.empty()) {
                throw runtime_error("Your stackMin is empty.");
            }
            return stackMin.top();
        }
    };
    
    int main()
    {
        MyStack1 stack1;
        stack1.push(4);
        cout << stack1.getMin() << endl; //4
        stack1.push(5);
        cout << stack1.getMin() << endl; //4
        stack1.push(2);
        cout << stack1.getMin() << endl; //2
        cout << stack1.pop() << endl;    //2
        cout << stack1.getMin() << endl; //4
    
    
        cout << "-----------------" << endl;
    
        MyStack2 stack2;
        stack2.push(4);
        cout << stack2.getMin() << endl; //4
        stack2.push(5);
        cout << stack2.getMin() << endl; //4
        stack2.push(2);
        cout << stack2.getMin() << endl; //2
        cout << stack2.pop() << endl;    //2
        cout << stack2.getMin() << endl; //4
    
        return 0;
    }

Mystack1：

push()：元素压入stackData；

stackMin为空，元素压入stackMin；

stackMin不为空，元素与其栈顶比较，元素小于等于则压入stackMin。

pop()：stackData弹出value；

若value等于（不可能小于）stackMin栈顶值，stackMin弹出栈顶元素。

Mystack2：

push()：元素压入stackData；

stackMin为空，元素压入stackMin；

stackMin不为空：

元素与其栈顶比较，元素小于等于栈顶元素，则压入stackMin；

元素大于栈顶元素，则将stackMin栈顶元素再次压入stackMin。