queue队列

学习顺序：

1. 学会使用STL的基本用法
2. 学会使用STL解决问题
3. 学会用一维数组模拟队列，解决问题

队列是限定在一端进行插入，另一端进行删除的特殊线性表

queue q;

queue<int> q;
q.push(3);
q.push(2);
q.push(5);
cout << q.front(); // 3
q.pop();
cout << q.front(); // 2

一维数组模拟队列

https://www.acwing.com/problem/content/831/

// 初始化，int hh = 0, tt = -1;     //Think about it: 莫队不也是这样吗？
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int hh = 0, tt = -1;
int main()
{
    int M;
    cin >> M;
    string op;
    int x;
    while (M--)
    {
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[++tt] = x; 
        }
        if (op == "pop")
        {
            hh++;            
        }
        if (op == "query")
        {
            cout << q[hh] << endl;
        }
        if (op == "empty")
        {
            if (hh <= tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
    }
    return 0;
}

《一本通》题目

【例2-1】周末舞会

//模拟两个队伍循环的过程，用两个指针模拟

【例2-2】Blah数集

//模拟从小到大生成数，计算方式可以是x = p[u]*2+1, y = p[v]*3+1;
//两种方法生成的数字，保留下来较小值
//只是这个较小值，有可能和已有的最后一个数字重复（这个写完程序，可以验证一下）
//开一个一维数组，从第0位开始，往右模拟生成数字

【例2-3】围圈报数

//用queue模拟出圈的过程

【例2-4】连通块

//flood fill
//用bfs实现

围成面积

//求*号围起来区域的面积
//如果能再*号里面开始bfs，显然是很简单的。那么，我们就思考如何能进入到*号的圈子里面
//flood fill算法，也是山峰和山谷的关系，这个*号就像是山峰，里面一个山谷，外面一个山谷
//火山口一样，那么填平外面的山谷，就只有里面的山谷了。思路描述到这，可以编程实现了

奇怪的电梯(lift)

//典型的最短路问题
//边权是1，可以用bfs实现

产生数(Produce)

//这道题目的规则是一位数字，转换成一位数字
//不是多位的转换，没那么复杂，可以直接暴力的干
//遇到坑，还是要多变换姿势求解
//最开始，我自己分析题意是，转换规则，可能是 ab -> cdd，这种变态的模式
//然后我就写了1个小时而已，写不出来了。主要是控制不好字符串替换中间一段的操作，存在开头和去尾的特殊位置
//感觉，这样出测试用例，肯定是一道好模拟题

家庭问题(family)

//这是一道并查集的问题
//优先去使用并查集实现，需要所有的点指向祖宗
//网上题解的实现代码都很啰嗦，建议看懂思路后，自己实现
//用开放链的方式模拟
//需要开设一个家庭就开设一个新家庭
//两人之间的关系用二维数组维护，类似邻接矩阵建图的操作
//开放链的遍历，和哈希函数的实现一样，从头开始遍历，遍历到有关系的人，就进入家庭
//如果没有遇到一个有关系的，就开一个新家庭
//一维数组实现队列
//感觉这种方法主要是锻炼h++ tail++的操作，思路和上一个一样。（未动手实践）

猴子选大王

//一般的猴子选大王，约瑟夫环问题，都是玩一个游戏，数一个固定的数m，数到就出圈
//这道题目是，从i个猴子开始数，就使用第i个规则数
//所以，这点在模拟的时候会不同。其他和普通的约瑟夫一样