备战蓝桥杯----数据结构及STL应用（基础2）

上次我们讲了vector的大致内容，接下来让我们讲一下栈，队列吧！

什么是栈呢？

很简单，我们用的羽毛球桶就是，我们取的球，是最后放的，栈是一种先进后出的数据结构。

方法函数

s.push(e)	e元素入栈
s.pop()	移除栈顶元素
s.top()	取得栈顶元素
s.empty()	判断栈是否为空
s.size()	返回栈内元素的个数

什么是队列呢？

队列是一种先进先出的数据结构，就像我们去上厕所，先排队的先上。

方法函数

q.front()	返回队首元素
q.back()	返回队尾元素
q.push(e)	尾部添加一个元素
q.pop()	删除第一个元素
q.size()	返回队列的元素个数
q.empty()	判断是否为空

接下来我们讲一下双端队列及优先队列：

双端队列（deque)

顾名思义，就是首尾都可插入和删除的数据结构（它可以用sort进行排序）

方法函数

d.push_back(x)/d.push_front(x)	把x插入队尾/队首
d.back()/d.front()	返回队尾/队首元素
d.pop_back()/d.pop_front()	删除队尾/队首元素
d.erase(iterator it)	删除某个元素
d.erase(iterator first,iterator last)	删除[first,last)的元素
d.empty()	判断其是否为空
d.size()	返回其元素数量
d.clear()	清空deque

优先队列（十分有用）

本质上是堆，由完全二叉树实现。

初始化定义：

#include<bits/stdc++.h>
using namespace std;
int main(){priorty_queue<int> q;}//定义

函数方法

q.top()	访问队首元素
q.push()	入队
q.pop()	队首元素出队
q.size()	队列元素个数
q.empty()	是否为空

设置优先级

#include<bits/stdc++.h>
using namespace std;
int main(){priority_queue<int> pq;//默认为大根堆priority_queue<int,vector<int>,greater<int>> q;//小根堆，int为堆中的数据类型priority_queue<int,vector<int>,less<int>> q;}//大根堆，int为堆中的数据类型