【C++】C++ STL探索：容器适配器 Stack 与 Queue 的使用及模拟实现（一）

一、Stack

1.1 stack介绍

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使用场景

1.3.1 最小栈

class MinStack
{
    public:
    /** initialize your data structure here. */
    void push(int x) 
    {
        _st.push(x);
        if(_minst.empty() || x <= _minst.top())
        {
            _minst.push(x);
        }
    }
    void pop()
    {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    int top() 
    {
        return _st.top();
    }
    int getMin() 
    {
        return _minst.top();
    }
    private:
    stack<int> _st;
    stack<int> _minst;
};

具体流程:

1. 创建一个栈，设置min的变量记录最小值。但是效率很低，如果插入或者删除数据，又需要重新遍历
2. 我们可以创建两个栈，一个用于插入或删除数据，一个用于记录栈中最小数。
3. 如果插入的数据比最小栈中栈顶数据要小，就插入在最小栈栈顶中。如果删除数据跟最小栈数据一样，需要同步删除，保持对其；如果删除数据不等于最小栈数据，单纯删除一边数据。

1.3.2 栈的弹出压入序列

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{
    stack<int> st;
    int pushi = 0; int popi = 0;
    while(pushi < pushV.size())
    {
        st.push(pushV[pushi++]);
        while(!st.empty() && st.top() == popV[popi])
        {
            popi++;
            st.pop();
        }
    }
    return st.empty();
}

具体思路:

1. 入栈序列不断入栈，在入栈期间判断栈顶元素和出栈序列是否匹配
2. 如果匹配，就需要持续出数据，直到不匹配或者栈为空（不一定结束）
3. 如果不匹配，那就继续入栈，等待下次匹配或结束
4. 结束标志:入栈序列走完后
5. 结果判断:栈不为空

1.3.3 何为中缀和后缀表达式

我们在实际中一般采用的是中缀表达式a+(b-c)，而后缀表达式是采用操作数、操作数、操作符的结构，转为这种形式的原因，是提供计算机使用的，中缀表达式给人看，一眼知道运算顺序，但是计算机不知道，需要转化后缀表达式进行运算（观察蓝色一圈圈圈起来的部分），遇到操作符就开始跟前面两操作数进行运算，返回一个数值。

1.3.4 逆波兰(后缀)表达式求值

class Solution
 {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        set<string> s = {"+","-","*","/"};
        
        for(auto str : tokens)
        {
            //如果等于操作符进行运算符
            if(s.find(str) != s.end())
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                     case '-':
                        st.push(left-right);
                        break;  
                    case '*': 
                        st.push(left * right);
                        break;  
                    case '/':
                        st.push(left / right);
                        break;      
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

具体流程:

1. 根据后缀表达式的工作原理，可以很快按照逻辑解决这道题目
2. 首先遇到操作符先入栈，如果遇到操作符就出栈两个操作数进行四则运算，并将结果入栈，等待下一次运算
3. 这里采用了set容器和stoi函数，简单介绍这两个函数的作用。
4. set是一个集合容器，存储唯一的元素，并且按照特定的顺序进行排序。
5. 使用s.find(str)时。从集合s中查找字符串str。如果str存在s集合中，find函数会返回一个指向该元素的迭代器，否则会返回s.end()，表达未找到该元素
6. stoi函数将字符串转换为整数，将一个标识数字的字符串转化为对应的整数类型，比如将"123"转化为整数123

1.3.5 中缀表达式转化为后缀表达式

• 中缀表达式:1 + 2 * 3 - 4
• 后缀表达式:1 2 3 * + 4 -

办法：

1. 操作数输出
2. 操作符

• 当栈为空，入栈
• 比栈顶的操作符优先级高，入栈
• 比栈顶的操作符优先级低或者相等，出栈操作符

3. 结束后，将栈中操作符，全部出栈

说明:这里关键为操作符，操作符出栈必有两个操作数在前面。同时存在两个操作符在栈中说明前面有三个操作符，即存在操作符的优先性。这里优先性是通过栈得以实现，优先级高的操作符先出栈。至于操作符的结合性就落到比栈顶的操作符优先级相等出栈操作符这块了。

1.3.6 深入探索：复杂表达式

如果是一个复杂的表达式，如何从中缀转化后缀表达式，进行运算呢？

例子: 1+2*（3+4/（2-1）+6）+5

办法:括号走递归，解决括号中表达式问题，将括号中顺序问题解决再添加到原本表达式中。

二、Queue

2.1 queue介绍

队列文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素(元素从队尾入队列，从队头出队列)
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设置的容器类。该底层应该至少支持以下操作

• empty:检测队列是否为空
• size:返回队列中有效元素的个数
• front:返回队头元素的引用
• back:返回队尾元素的引用
• push_back:返回队尾元素的引用
• pop_front:在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。（这里容器选择不适合vector，因为没有头删，如果使用erase效率也很低）

2.2 queue使用

【C++】C++ STL探索：容器适配器 Stack 与 Queue 的使用及模拟实现（二）https://developer.aliyun.com/article/1617375