stack 和 queue容器的介绍和使用

1.stack的介绍

1.1stack容器的介绍

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

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

1.2 stack的使用

函数说明	接口说明
stack	构造空的栈
empty	检测stack是否为空
size	查看栈中元素的数量
top	获取栈顶元素
push	将元素压入栈中
pop	将栈顶元素删除

常用的接口基本是哪个就是上面的这些,现在我们万层下面的练习题来熟练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 hereif (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接口介绍

函数声明	接口说明
queue	构造空的队列
empty	检测队列是否为空，是返回true, 否则返回false
size	返回队列中的元素
front	返回对头元素的引用
back	返回队尾元素的引用
push	在队尾将元素val插入队列
pop	将对头元素出队列

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()/priority_queue(first,last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

注意：在默认情况下，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不是这道题最优的解法，大家可以下去自己探索哈 😛