队列（Queue）是C++中重要的数据结构，遵循先进先出（FIFO）原则。

---

一、队列的基本操作

1. 头文件与定义

#include <queue>         // 引入队列头文件
queue<int> q;            // 定义整型队列q

2. 核心操作函数

函数	功能	示例
push(x)	元素x入队	q.push(10);
pop()	队首元素出队（需先判空）	q.pop();
front()	获取队首元素（不删除）	int x = q.front();
back()	获取队尾元素（不删除）	int y = q.back();
size()	返回队列元素个数	int len = q.size();
empty()	判断队列是否为空（空返回true）	if(q.empty())...

---

二、队列的典型应用场景

案例1：约瑟夫环问题（报数出列）

问题描述
n个人围成一圈，从1开始报数，数到m的人出列，求最后剩下的人。

解决思路

• 用队列模拟循环报数过程

• 未报到m时，队首元素出队并重新入队

• 报到m时直接出队，不重新入队

代码实现

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for(int i=1; i<=n; i++) q.push(i);
    
    while(q.size() > 1) {
        for(int k=1; k<m; k++) {  // 前m-1个元素重新入队
            q.push(q.front());
            q.pop();
        }
        q.pop();  // 第m个元素出队
    }
    cout << q.front();
    return 0;
}

案例2：舞伴配对问题

问题描述
男女两队循环配对，每对舞伴跳完后回到队尾，输出前k对组合。

解决思路

• 使用两个队列分别存储男女编号

• 每次取队首配对后重新入队

代码实现

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    queue<int> male, female;
    for(int i=1; i<=m; i++) male.push(i);
    for(int i=1; i<=n; i++) female.push(i);
    
    while(k--) {
        int b = male.front(), g = female.front();
        cout << b << " " << g << endl;
        male.pop(); female.pop();
        male.push(b); female.push(g);
    }
    return 0;
}

案例3：新兵队列训练

问题描述某部队进行新兵队列训练，将新兵从1开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始1至2报数，凡报到2的出列，剩下的向小序号方向靠拢，再从头开始进行1至3报数，凡报到3的出列，剩下的向小序号方向靠拢；继续从头开始进行1至2报数……，以后从头开始轮流进行1至2报数、1至3报数直到剩下的人数不超过三人为止。

输入：N，表示新兵人数。 输出：剩下的新兵最初的编号，空格隔开。

输入样例1：20 输出样例1：1 7 19

输入样例2：40 输出样例2：1 19 37

解决思路

• 使用两个队列交替处理不同报数规则

• 动态调整队列元素

代码实现

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<int> q;
    for(int i=1; i<=n; i++) q.push(i);
    
    bool flag = true;  // 标记当前报数模式
    while(q.size() > 3) {
        int len = q.size();
        for(int i=0; i<len; i++) {
            int x = q.front();
            q.pop();
            // 根据当前模式保留元素
            if(flag && (i+1)%2 != 0) q.push(x);
            if(!flag && (i+1)%3 != 0) q.push(x);
        }
        flag = !flag;  // 切换模式
    }
    
    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

---

三、队列使用技巧总结

1. 判空优先：调用front()或pop()前必须用empty()判断

2. 循环处理：通过push(pop())实现元素循环利用

3. 交替队列：使用多个队列处理复杂逻辑（如新兵训练）

4. 复杂度：所有操作时间复杂度为O(1)