stack 和 queue容器的介绍和使用

1.stack的介绍

1.1stack容器的介绍

stack容器的基本特征和功能我们在数据结构篇就已经详细介绍了，还不了解的uu， 可以移步去看这篇博客哟：

• 数据结构-栈
• 数据结构-队列
  
  简单回顾一下，重要的概念其实就是后进先出，栈在实际的工程中有着广泛的用途·，所以在c++的stl库中自然也有它的身影。

1.2 stack的使用

常用的接口基本是哪个就是上面的这些,现在我们万层下面的练习题来熟练stl库中的stack容器。

1.2.1 最小栈

题目链接

这道题目非常的特殊，这道题目就是需要我们自己来设计函数接口，来满足题目所需：
这都啊题目需要我们实现一个可以在常数时间内锁定stack中最小元素的Minstack类：

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        
    }
    
    void pop() {
        
    }
    
    int top() {
        
    }
    
    int getMin() {
        
    }
};

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

现在我们要实现下面的接口，其实这道题目也并不复杂，我们只需要定义两个栈

• 一个栈用于记录此时栈中所有的元素
• 一个用于记录栈中所有的元素

1.关于怎么来记录此时容器中最小的元素，我们就只需要在元素入栈的时候进行比较就可以实现
2. 只要遇到比记录最小值栈的栈顶元素小的元素，我们就直接让其成为栈顶

有了基本的思路后大家可以自己尝试一下这道题目 😛:
好了，相信大家已经做出来了，现在我们就来展示一下答案吧：🌈

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
    //注意：这里一定是小于等于，在st种可能存在多个最小值
        if (_min.empty() || val <= _min.top()) _min.push(val);
        st.push(val);
    }
    
    void pop() {
        if (st.top() == _min.top()) _min.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
       return _min.top();
    }
private:
    stack<int> st;
    stack<int> _min;
};

1.2.2 栈的弹出压入序列

题目链接

这都题目就是需要我们根据栈的后进先出的特性来进行判断，其实在了解了stack的基本特性后也是十分的简单的， 接下来我就直接展示代码了：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        if (pushV.size() != popV.size() ) return false;

        int n = pushV.size();
        int out = 0, in = 0;
        stack<int> s;
        while (out < n)
        {
            while (s.empty() || s.top() != popV[out])
            {
                if (out < n)
                s.push(pushV[in++]);
                else return false;
            }
            s.pop();
            out++;
            
        }
        if (!s.empty()) return false;;
        return true;
    }
};

完成了上面的题目相信大家都已经对stack容器的使用很熟悉了，那我们就进入queue的学习了 😛

2. queue容器的介绍和学习

队列（queue）系那个寻大家爱都已对此十分的熟悉了，大家在学习之前也可以先来阅读以下下面的这篇文档哈 🌈 🌈
和stack一样，在stl中我们也可以直接使用他提供的众多接口，下面就是我们常用的一些接口：

2.1 queue接口介绍

2.2 queue相关的题目

为了熟悉上那面的接口，我们还是通过练习下面的题目来巩固我们的学习：

2.2.1 用队列实现栈

题目链接

这道题目还是十分简单的，我们知道了 stack 和 queue对于数据的存取顺序的区别，需要使得后面插入的元素在队列的前端 ：
现在大家可以在得到提示后可以先舱室自己做一下哈，下面我就直接展示代码了：

class MyStack {
public:
queue<int> qu;
    MyStack() {
        
    }
    
    void push(int x) {
        int n = qu.size();
        qu.push(x);
        while (n--)
        {
            int t = qu.front();
            qu.pop();
            qu.push(t);
        }

    }
    int pop()
    {
        int a = qu.front();
        qu.pop();
        return a;
    }
    
    int top() {
        return qu.front();
    }
    
    bool empty() {
        return qu.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

3. priority_queue的介绍和使用

3.1priority_queue的介绍

介绍文档
介绍：

1. 优先队列是一种容器适配器，更具严格的弱排序标准，他的第一个元素总是它所包含元素的中的最大值
2. 类似于堆， 在堆中随时插入元素，并且只能检索最大的堆中元素 （优先队列中位于顶部的元素）
3. 优先队列被实现为容器适配器，容器适配器即将特定的容器封装为其底层的容器类，queue提供的一组特定的成员函数来访问其元素。元素从特定的容器“尾部”弹出，其被称为优先队列的顶部
4. 底层的容器可以是任何标准的类模板，也可以是其他特定的设计类模板。容器应该可以通过随机访问迭代器访问，并支持以下的操作：

   • empty()：检测容器是否为空
   • size()：返回容器中有效元素个数
   • front()：返回容器中第一个元素的引用
   • push_back()：在容器尾部插入元素
   • pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue
   类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用
   算法函数make_heap、push_heap和pop_heap来自动完成此操作。

3.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中
元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用
priority_queue。注意：默认情况下priority_queue是大堆。

3.2.1 常用接口的介绍

注意：在默认情况下，priority_queue就是大堆, 想要将其改为小堆需要一个greater<T>的类模板

#include <vector>
#include <queue>
#include<iostream>
using namespace std;
void TestPriorityQueue()
{
    // 默认情况下，创建的是大堆，其底层按照小于号比较
    vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
    priority_queue<int> q1;
    for (auto &e : v)
        q1.push(e);
    cout << q1.top() << endl;

    // 如果要创建小堆，将第三个模板参数换成greater比较方式
    priority_queue<int, vector<int>, greater<int>>
        q2(v.begin(), v.end());
    cout << q2.top() << endl;
}

int main()
{
    TestPriorityQueue();
    return 0;
}

总而言之，priority_queue就像是我们再数据结构中学到的堆的具体应用，现在我们就还是通过题目来熟练使用stl的优先队列吧 ✈️

3.3 priority_queue在OJ题目中的应用

数组中的第K个大的元素

题目中要求我们使用O(N)的时间复杂度来解决这个问题，因此我们不能直接对数组进行排序，然后直接找对应位置的元素，因为快速排序的时间复杂度是Nlog(N)
因此我们就需要用到我们刚学习的容器来解决这个问题了，其实也十分的简单，大家：自己尝试着做

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto& x : nums)
        {
            q.push(x);
            if (q.size() > k) q.pop();
        }
        return q.top();
    }
};

这样我们看就可以以O(N)的时间复杂度完成这道题目了！！

注： 使用priority_queue不是这道题最优的解法，大家可以下去自己探索哈 😛