队列

学习顺序：

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

例题，2037：【例5.4】约瑟夫问题

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);
    int k = 0;
    while (!q.empty()){
        k++;
        int t = q.front(); q.pop();
        if (k == m){
            k = 0;
            printf("%d ", t);
            continue;
        }
        q.push(t);
    }
    puts("");
    return 0;
}

一维数组模拟队列

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-3】围圈报数

//用queue模拟出圈的过程

例题，猴子选大王

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

例题，【例2-1】周末舞会

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

例题，产生数(Produce)

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