• 手写普通队列
//hh表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;

//向队尾插入一个数
q[++ tt] = x;

//从队头弹出一个数
hh ++;

//队头的值
q[hh];

//判断队列是否为空
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];

//判断队列是否为空
if (hh != tt){
  
}
  • STL中的queue
#include<queue>
头文件queue 主要包括循环队列 queue 和优先队列 priority_queue 两个容器

- 声明
queue<int> q;
struct rec{...}; queue<rec> q; //结构体rec中必须定义小于号
//如果是大根堆则要重载小于号
struct Rec{
    int a, b;
    bool operator< (const Rec& t) const
    {
        return a < t.a;
    }
};

priority_queue<int> q; // 大根堆
priority_queue<int, vector<int>, greater<int>> q; // 小根堆，结构体重载大于号
priority_queue<pair<int, int>>q;
           
- 循环队列queue
push //从队尾插入
pop //从队头弹出
front // 返回队头元素
back // 返回队尾元素

- 优先队列priority_queue
push //把元素插入堆
pop //删除堆顶元素
top //查询堆顶元素（最大值）
  • 手写队列在bfs中的应用
题目：
农场上起火了，奶牛们正在紧急赶去灭火！

农场可以用一个像这样的 10×10 的字符方阵来描述：

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
字符’B’表示正着火的牛棚，字符’L’表示一个湖，而字符’R’表示农场上的一块巨大岩石。

奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。

当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。

湖边的奶牛也是如此——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。

类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。

请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的’.’格子的最小数量。

奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。

输入格式
输入包含 10 行，每行 10 个字符，描述这个农场的布局。

输入保证图案中恰有一个字符’B’、一个字符’L’以及一个字符’R’。

输出格式
输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。

输入样例：
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
输出样例：
7
样例解释
在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：

..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........

题解：
#include<bits/stdc++.h>

using namespace std;

const int N = 11;
typedef pair<int ,int>PII;
// g[N][N]用来储存地图，d[N]][N]用来储存距离
char g[N][N];
int d[N][N];
//队列
PII q[N * N];
int lx, ly;

void bfs(){
  	//实现队列
	int hh = 0, tt = -1;
  	//加入队头元素
	q[++ tt] = {lx, ly};
  	//初始化d数组，即所有点到起点距离都是-1，起点自身距离为0
	memset(d, -1, sizeof d);
	d[lx][ly] = 0;
  	//记录偏移量
	int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
	while (hh <= tt){
		auto t = q[hh ++];
      	//拓展队列
		for (int i = 0; i < 4; i ++){
			int x = t.first + dx[i], y = t.second + dy[i];
			if (x >= 0 && x < 10 && y >= 0 && y < 10 && g[x][y] != 'R' && d[x][y] == -1){
				if (g[x][y] == 'B'){
					cout << d[t.first][t.second];
					return;
				}
				d[x][y] = d[t.first][t.second] + 1;
				q[++ tt] = {x, y};
			}
		}
	}
}

int main(){
	for (int i = 0; i < 10; i ++)
		for (int j = 0; j < 10; j ++){
			cin >> g[i][j];
          //记录下湖的位置，也即即将用到的队头
			if (g[i][j] == 'L')
				lx = i, ly = j;
		}

	bfs();

	return 0;
}