队列及模板
1. 队列的定义
队列也是操作受限的线性表，满足先进先出特性。
2. 数组模拟队列
在这里，我们采用数组q来模拟队列，hh代表队头指针，tt代表队尾指针。
队列的常用操作如下：
1. 往队列中插入一个元素
q[++tt] = x;
2. 往队列中弹出一个元素
hh++;
3. 判断队列是否为空
if(hh <= tt){
not empty;
}else{
empty;
}
4. 取出队头和队尾元素
q[hh]
q[tt]
5. 在以上操作下，队列的初始化
hh = 0;
tt = -1;
3. 队列的模板
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}
这里补充一下循环队列的模板
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{
}
4. 例题
https://www.acwing.com/problem/content/831/
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int q[N];
int hh = 0;
int tt = -1;
void push(int x){
q[++tt] = x;
}
void pop(){
hh++;
}
void empty(){
if(hh <= tt){
printf("NO\n");
}else{
printf("YES\n");
}
}
int query(){
return q[hh];
}
int main(){
int m,x;
string op;
scanf("%d",&m);
while(m--){
cin >> op;
if(op == "push"){
scanf("%d",&x);
push(x);
}else if(op == "pop"){
pop();
}else if(op == "query"){
printf("%d\n",query());
}else{
empty();
}
}
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。