示意图
什么是队列
队列（queue）是一种具有 先进入队列的元素一定先出队列 性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。就像排队一样，最先到的人也就最先买到单，优先离开队伍
头文件与声明
头文件
#include <queue>
声明定义
queue<G> que;
//G —— 数据类型
用数组模拟栈
定义
int q[SIZE], ql = 1, qr;
//SIZE：长度
//ql：队尾
//qr：队头
插入
q[++qr] = x;
删除
ql++;
访问队首
q[ql]
访问队尾
q[qr]
清空
ql = 1, qr = 0;
长度
qr - ql + 1
为空
ql == qr + 1
其实双栈也可以实现1
STL queue 常用函数
V 为要操作的元素
-
元素访问
que.front()访问队首元素que.back()访问队尾元素
-
修改
que.push(V)在队尾插入元素 V V Vque.pop()弹出队首元素
-
测量
que.empty()判断容器是否为空（空返回1，有返回0）que.size()查询容器的长度（元素数量）
-
运算符
queue重载了 ” = = =“ 运算符，q1 = q2;将队列 q 1 q1 q1 的所有元素赋给 q 2 q2 q2
特殊队列
双端队列
定义
双端队列是指一个可以在队首和队尾执行普通队列操作的队列。
头文件
#include <deque>
声明
deque<G> deq;
//G —— 数据类型
STL deque 常用函数
V 为要操作的元素
-
元素访问
que.front()访问队首元素que.back()访问队尾元素
-
修改
que.push_back(V)在队尾插入元素 V V Vque.pop_back()弹出队首元素que.push_front(V)在队首插入元素 V V Vque.pop_front()弹出队首元素
-
测量
que.empty()判断容器是否为空（空返回1，有返回0）que.size()查询容器的长度（元素数量）
-
运算符
deque也同queue一样重载了 ” = = =“ 运算符- 重载
[]，可以像数组访问元素
优先队列
<queue> 中还提供了优先队列
G —— 数据类型
- 大根堆
priority_queue<G, vector<G>, less<G> > pq;//完整版
priority_queue<G> pq;//化简版
- 小根堆
priority_queue<G, vector<G>, greater<G> > pq;//完整版
循环队列
一种优化方式，对于用数组模拟的栈有效。
随着时间的推移，栈序列将达到数组尾部，而前端却是空的，此时在进行插入则会导致溢出，称为〔假溢出〕。
这时就需要采取循环的方法，类似循环链表，数组最后一位的下一个直接连着第一位，提高利用率，这就有了循环队列。
例题
洛谷B3616
考察对队列的理解。
操作在题目中十分明显，按照题意模拟即可
#include<bits/stdc++.h>
using namespace std;
int n, m, op, x;
queue<int> q;
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> op;
if(op == 1){
cin >> x;
q.push(x);//插入
}
else if(op == 2){
if(q.empty()){
cout << "ERR_CANNOT_POP\n";//要判断是否为空，否则RE
}
else{
q.pop();//如果不为空，弹出
}
}
else if(op == 3){
if(q.empty()){
cout << "ERR_CANNOT_QUERY\n";//判空
}
else{
cout << q.front() << endl;//输出第一个
}
}
else{
cout << q.size() << endl;//输出队列大小
}
}
return 0;
}
使用小根优先队列，每此将最小的两个数合并后重新入队，同时统计耗费
代码：
#include<bits/stdc++.h>
using namespace std;
priority_queue <int, vector<int>, greater<int> > q;
int n, sum, c, d;
int main(){
cin >> n;
for(int i = 1, x; i <= n; i++){
cin >> x;
q.push(x);
}
while(q.size() > 1){
c = q.top();
q.pop();
d = q.top();
q.pop();
q.push(c + d);
sum += c + d;
}
cout << sum;
return 0;
}
End \Huge\color{Grey}\text{End} End
push：插入到栈 F 中。
pop：如果 S 非空，让 S 弹栈；否则把 F 的元素倒过来压到 S 中（其实就是一个一个弹出插入，做完后是首尾颠倒的），然后再让 S 弹栈。
容易证明，每个元素只会进入/转移/弹出一次，均摊复杂度 O(1)。来源：oi-wiki
这种方法使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作： ↩︎