题目来源

• leetcode：716-VIP. 最大栈

题目描述

题目解析

使用两个栈来模拟，dataStack为普通的栈，用来保存所有的数字，而maxStack为最大栈，用来保存出现的最大的数字。

class MaxStack{
    std::stack<int> stack;
    std::stack<int> max_stack;
public:
    MaxStack(){

    }

    void push(int x){
        stack.push(x);
        if(max_stack.empty() || x >= max_stack.top()){
            max_stack.push(x);
        }
    }

    int pop(){
        if(!max_stack.empty() && max_stack.top() == stack.top()){
            max_stack.pop();
        }
        int t = stack.top(); stack.pop();
        return t;
    }

    int top(){
        return stack.top();
    }

    int peekMax(){
        return max_stack.top();
    }

    int popMax(){
        int max = max_stack.top();
        // 先将最大值之上元素的保存起来
        std::stack<int> t;
        while (stack.top() != max){
            t.push(stack.top()); stack.pop();
        }
        // 弹出最大值
        stack.pop(); max_stack.pop(); 
        // 将t中的元素倒回去
        while (!t.empty()){
            push(t.top()); t.pop();
        }
    }
};

类似题目