【算法训练营】STL算法 Stack 栈的压入、弹出序列+最小栈

Stack刷题

• 1.最小栈
• 2.栈的压入、弹出序列

1.最小栈

题目链接: 最小栈

• 题目描述
  

• 解决思路 创建一个辅助栈 只保存最小的元素

• 代码

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        // 只要是压栈，先将元素保存到_elem中
        _stack.push(val);
        //然后判断minstack是否有元素  有元素还要判断栈顶元素是否比当前插入元素大 最小的插入
        if(_minstack.empty()||val<=_minstack.top())
        {
            _minstack.push(val);
        }
    }
    
    void pop() {
        if(_stack.top()==_minstack.top())
        {
            _minstack.pop();
        }
        _stack.pop();
    }
    
    int top() {
        return _stack.top();
    }
    
    int getMin() {
        return _minstack.top();
    }
    std::stack<int> _stack;
    std::stack<int> _minstack;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2.栈的压入、弹出序列

题目链接: 栈的压入、弹出序列

• 题目描述
  
• 题解
  
  
• 代码

class Solution {
  public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        stack<int> stack;//创建一个辅助栈
        //当两个栈为空或者大小不相等的时候直接return false
        if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
            return false;

        int idx = 0;
        for (int num : popV) {
            while (stack.empty() || stack.top() != num) {
                // 如果压入序列已经遍历完成，则退出循环
                if (idx >= pushV.size())
                    break;

                stack.push(pushV[idx]);
                idx++;
            }
            // 在执行pop操作前进行判断
            if (!stack.empty() && stack.top() == num)
                stack.pop();
            else
                return false; // 如果栈顶元素与当前弹出序列不匹配，则返回false
        }

        // 检查栈是否为空
        return stack.empty();
    }
};