【c++】STL之stack和queue详解

> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：掌握stack和queue库，了解deque库

> 毒鸡汤：小时候，哭是我们解决问题的绝招，长大后，笑是我们面对现实的武器。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

今天咱们学习stack和queue，咱们还是依照官网来学习：

stack - C++ Reference (cplusplus.com)

queue - C++ Reference (cplusplus.com)

⭐主体

在数据结构初阶中，我们模拟实现了stack和queue，只能说我们知道栈和队列，但是栈和队列的底层是如何实现的我们就不得而知了，面对这个现象我们从新学习栈和队列，深度解剖。学习这个版块，咱们按照下面的图解进行学习：

🌙stack的介绍和使用

💫stack的介绍

stack - C++ Reference (cplusplus.com)

stack是一种容器适配器，其本质是数据结构中的栈。它是一种只能在一端进行插入和删除操作的线性表。
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，
默认情况下使用deque。
栈和队列都叫做适配器/配接器，不是直接实现的，而是封装其他容器，包装转换实现出来的
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下：

empty：判空操作。
back：获取尾部元素的操作，这是因为栈的top操作相当于拿取尾部元素。
push_back：尾部插入元素操作。
pop_back：尾部删除元素操作。

💫stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

代码训练：

#include<iostream>
#include<stack>
#include<queue>

using namespace std;

void test_stack()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    
    cout << st.empty() << endl; // 检测stack是否为空
    cout << st.size() << endl;  // 返回stack中元素的个数
    
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}
int main()
{
    test_stack();
    return 0;
}

代码训练：tack的案例，首先先创建一个stack容器，<int>这里表示我这个容器存放的是int类型的数据。然后通过push()将数据压入栈中，stack并不支持迭代器访问，我们通过接口empty()判断栈是否为空，通过top()访问栈顶元素，pop()将数据出栈。

💫stack的应用

1.155. 最小栈 - 力扣（LeetCode）

问题分析：设计两个栈，一个负责保存栈的元素，一个负责保存栈的最小值。只要有元素比最小值栈的顶部元素还有小，那么，就将这个值压入最小值栈中，这样就能保证，最小值栈的顶部元素永远是当前压入的所有元素中最小的。

代码：

class MinStack {
public:
    MinStack() 
    {

    }
    
    void push(int val) 
    {
        st.push(val);
        if(minst.empty() || val <= minst.top())
        {
            minst.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; // 辅助栈
};

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

问题分析：借助一个辅助栈，首先，创建两个变量i和j，分别指向pushV数组的元素和popV数组的元素，然后将pushV的数据压入栈中，直到遇到顶部元素恰好等于出栈序列的元素，那么就将栈顶元素出栈，并且j++。最后，如果栈的元素不为空，那么说明当前出栈序列不符合。

代码：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) 
    {
        stack<int> st;
        int i = 0, j = 0; // i 指向push数组的元素 ， j 指向pop数组元素
        for(; i < pushV.size();i++)
        {
            st.push(pushV[i]);
            while(!st.empty() && st.top() == popV[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

3.150. 逆波兰表达式求值 - 力扣（LeetCode）

问题分析：同样借助一个辅助栈来完成，遍历数组tokens，遇到数值就压入栈中，遇到符号，就弹出两个元素，并且根据符号进行求值。最后，栈顶元素就是最终的表达式结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        for(int i = 0;i<tokens.size();++i)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num2 + num1);
                else if(tokens[i] == "-") st.push(num2 - num1);
                else if(tokens[i] == "*") st.push(num2 * num1);
                else if(tokens[i] == "/") st.push(num2 / num1);
            }
            else 
            {
                st.push(stoi(tokens[i])); // stoi 把字符串转为数字
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};

4.232. 用栈实现队列 - 力扣（LeetCode）

问题分析：设计两个栈，一个栈用来入数据，一个栈用来出数据。入队列操作，可以直接将数据插入到stIn中，出队列的时候，如果stOut为空，就将stIn的数据放到stOut中，我们直到栈的特性是后进先出，队列的特性是先进先出，那么将元素放到一个栈中，再出栈到另一个栈中，相当于元素原本的顺序不变，恰好符合队列的要求。

代码：

class MyQueue {
public:
    stack<int> stIn;  // 用来入数据
    stack<int> stOut; // 用来出数据
    MyQueue() 
    {

    }
    
    void push(int x) 
    {
        stIn.push(x);
    }
    
    int pop() 
    {
        if(stOut.empty())
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    // 获取头部元素
    int peek() 
    {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() 
    {
        return stIn.empty() && stOut.empty();
    }
};

🌙queue的介绍和使用

💫queue的介绍

queue - C++ Reference (cplusplus.com)

queue是一种容器适配器，专门用于在先进先出上下文中操作，在容器的一端插入元素，另一端删除元素。

queue的底层也是用作容器来进行封装，底层容器必须支持以下操作：

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

标准容器中的deque、list满足了这些要求，默认情况下，使用deque作为底层容器类。

💫queue的使用

函数说明	接口说明
empty	检测queue是否为空
size	返回queue的元素个数
front	返回队头元素的引用
back	返回队尾元素的引用
push	在队尾将元素入队列
pop	将队头元素出队列

代码训练：

#include<iostream>
#include<stack>
#include<queue>

using namespace std;

void test_queue()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    cout << q.empty() << endl;
    cout << q.size() << endl;
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}
int main()
{
    test_queue();
    return 0;
}

运行结果：

💫queue的应用

225. 用队列实现栈 - 力扣（LeetCode）

问题分析：使用两个队列，重点在于出栈操作，出栈操作，将队列1的元素，放到队列2，队列1的元素只剩下1个，然后这个作为出栈的元素，之后q1 = q2，然后将q2的元素进行出队。

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size = q1.size();
        size--;
        while(size--)
        {
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        q1 = q2;
        while(!q2.empty())
        {
            q2.pop();
        }
        return result;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};