【C++栈和队列：数据结构中的经典组合，高效处理先进先出与后进先出问题的最佳方案】_c++ 现有两个满足先进出原则的队列 现有两个满足先进出原则的队列 现有两个满足先

[本节目标]

• 1. stack的介绍和使用

• 2. queue的介绍和使用

• 3. priority_queue的介绍和使用

• 4. 容器适配器

1. stack的介绍和使用

1.1 stack的介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

1.2 stack的使用

1.3 stack题目的练习

​​​​​​155. 最小栈 - 力扣（LeetCode）

我们来看看这个题目的解题思路，我们首先来看一种错误的解题方法，看看它为什么错误。

错误思路：将数组中的值依次入栈，此时定义一个变量min去记录最小值，当入栈的值比min小，更新min的值。

我们来看看这个思路为什么错误，如果栈中途没有元素出栈，那么这个思路完全正确，因为入栈的过程相当于把这个栈遍历了一遍，此时就可以找到最小值，可是当我们有元素出栈呢？我们看看上面的图片，此时已经找到最小值了3，可是随后3出栈了，但是此时的min该如何变化呢？此时找min就需要再遍历一次栈，所以这个思路是行不通的。

正确思路：建立两个栈，一个普通栈正常入数据，另外一个最小栈入栈最小值，当普通栈为空的时候，此时该值就直接入最小栈，当普通栈入栈的数据大于上次最小值入栈的值时，此时再次将上次的最小值入最小栈，当普通栈入栈的数据小于上次最小值入栈的值时，此时将这个小值入最小栈，如果要取出最小值的时候，只需要取最小栈的栈顶值即可。

我们能不能再进一步优化呢？我们上面的最小栈没必要存储那么多的元素5，当普通栈栈顶元素 > 最小栈栈顶元素的时候，此时就不需要入栈，但是普通栈栈顶元素 = 最小栈栈顶元素的时候，我们需要入最小栈。

解题代码：

class MinStack {
public:
    MinStack() {
        //这里可以不用写
        //自定义类型会去调用自己的默认构造
    }
    
    void push(int val) {
        st.push(val);
        if(minst.empty() || st.top() <= minst.top())
        {
            minst.push(val);
        }
    }
    
    void pop() {
        if(st.top() == minst.top()) minst.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }
    stack<int> st;
    stack<int> minst;
};

此时面试官又会提一个问题，如果入普通栈的数据全部都是3呢？按照我们上面的逻辑，此时最小栈也要全部存3，那么我们上面的优化就相当于没有优化，此时我可以通过计数器来解决，当普通栈有多个相同值时，此时最小栈入栈还可以存储一个计数器，每次入最小栈的时候++count；栈每次pop的时候只需要--count，当减到0的时候就可以删除3。

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

解题思路：题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，我们让它入栈，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。