一、栈和队列的使用

由于栈要保持其结构特点（进出数据是后进先出），栈是不支持迭代器的

在这里插入图片描述

队列的头文件下有两个队列，一个叫普通队列，一个叫优先级队列，优先级队列更复杂一些，其底层的结构就是堆

在这里插入图片描述

二、栈和队列相关算法题

2.1 最小栈

最小栈

在这里插入图片描述

这里的解决方法是用两个栈，第一个栈st是正常的栈，第二个栈minst用来记录最小数据，左边的栈进一个4，右边栈也进一个4，只要插入的数据比前一个数据小，minst这个栈就进数据，或者minst为空，也进数据，以此类推

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

此时当所有数据插入完成后，再进行pop，getMin就可以获得2了

还有一个点，若左边插入和右边一样大小的值，右边的栈也要插入

在这里插入图片描述

例如现在插入和1一样大小的值，右边不插入的话，此时若pop（左边删除的值若和右边的值相等，则右边也要删除，要更新下一个最小值，但是下一个左边删除6，右边的值是不删除的），右边的1被删除后，更新的下一个最小值变为2了，但实际上最小值为1

在这里插入图片描述

代码语言：javascript

AI代码解释

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        if(_minst.empty() || val <= _minst.top())
            _minst.push(val);
        _st.push(val);
    }
    
    void pop() {
        if(_minst.top() == _st.top())
            _minst.pop();
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
private:
    stack<int> _st;
    stack<int> _minst;
};

/**
 * 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();
 */

说一下这里代码的构造过程 MinStack的私有成员是两个stack< int >类型的对象：

• _st：主栈，用于存储所有元素；
• _minst：辅助栈，用于存储当前栈中的最小值。 当创建一个MinStack对象时（比如MinStack ms;），构造过程会按以下步骤执行：

步骤 1：自动初始化成员对象（_st和_minst） 在执行MinStack的构造函数体之前，C++ 会先自动调用成员对象自身的默认构造函数：

• _st会调用stack< int >的默认构造函数，初始化一个空的主栈；
• _minst会调用stack< int >的默认构造函数，初始化一个空的辅助栈。

（注：stack是 STL 容器，它的默认构造函数本身就是创建一个空栈）

步骤 2：执行MinStack的构造函数体 显式定义的MinStack()构造函数体是空的（{}），所以这一步没有额外操作。

当然把MinStack()构造函数删了也可以

2.2 栈的压入、弹出序列

栈的压入、弹出序列

在这里插入图片描述

一个栈的一种压入顺序可能对应多种弹出顺序，比如图中所给样例1

代码语言：javascript

AI代码解释

[1,2,3,4,5],[4,5,3,2,1]

先压入1，2，3，4。然后弹出4，再压5，之后弹出5，再弹出3，2，1

在这里插入图片描述

所以说该序列就是一个合法序列

对于样例2来说

代码语言：javascript

AI代码解释

[1,2,3,4,5],[4,3,5,1,2]

先压入1，2，3，4。然后弹出4，3

在这里插入图片描述

再压入5，弹出5

在这里插入图片描述

然而接下来就不可能先弹出1了，按照结构应该先弹出2，所以该序列就是不合法的所以核心思路就是使用一个栈来模拟这个过程