队列

队列是一种 先进先出（First-In, First-Out, FIFO） 的数据结构。可以把它想想成现实生活中的排队。

• 入队（Enqueue/Push）：新来的人总是站到队伍的末尾。
• 出队（Dequeue/Pop）：每次办理业务的总是站在队伍最前面的人。
• 队头（Front）：队伍的最前面。
• 队尾（Back/Rear）：队伍的末尾。

---

数组实现

最直接、最朴素的实现队列的想法是什么？

1. 准备一个足够大的数组 q。
2. 用一个指针 tail（队尾）来记录新元素应该插入的位置。每次入队，tail 就向后移动。
3. 用一个指针 head（队头）来记录队头元素的位置。每次出队，head 就向后移动。

选择题：下述代码实现的数据结构是

int data[100], f = 1, r;
void insert(int value) {
	data[++r] = value;
}
void pop() {
	f++;
}

A. 链表
B. 栈
C. 队列
D. 平衡树

答案

C

---

P1540

#include <cstdio>
#include <queue>
using std::queue;
const int N = 1005;
bool inq[N]; // inq[i]表示i是否在队列中
int main()
{
	int m, n; scanf("%d%d",&m,&n);
	queue<int> q;
	int cnt=0; // 队列中元素个数
	int ans=0;
	for (int i=1;i<=n;i++) {
		int x; scanf("%d",&x);
		if (!inq[x]) {
			if (cnt>=m) {
				inq[q.front()]=false;
				cnt--;
				q.pop();
			} 
			q.push(x); inq[x]=true; cnt++;
			ans++;
		}
	}
	printf("%d\n",ans);
    return 0;
}

例题：UVA540 团体队列 Team Queue

可以抽象为两个层级的队列结构：

1. 主队列：维护排队团队的顺序，队列中的元素是“团队编号”。
2. 团队子队列：维护每个团队内部成员的排队顺序，每个团队都有一个独立的队列。

为了高效地实现逻辑，需要一个团队映射数组记录每个人所属的团队 ID，这个数组在读取所有团队信息时构建。

当处理 ENQUEUE x 操作时，查找 \(x\) 所属的团队 ID，检查该团队是否已经在排队，如果对应的团队子队列为空，说明该团队之前没人，现在来了第一个人，需要把这个团队 ID 加入到主队列的末尾。而无论是否是新来的团队，都将 \(x\) 加入到该团队的子队列中。

当处理 DEQUEUE 操作时，找到主队列队首的团队 ID，输出该团队子队列队首的成员，将该成员出队。关键点在于，如果出队后，该团队的子队列变空了，说明该团队目前没人了，需要将该团队 ID 从主队列中移除，这样下一个排队的团队就变成了主队列的队首。

这种设计模拟了题目要求的插队逻辑：有队友时进入队友所在的子队列（相当于插到了队友后面），没队友时团队 ID 进主队列末尾（相当于排在整个队伍最后）。

参考代码

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

// team[id] 存储编号为 id 的人所属的团队编号
int team[1000000];
// tq[i] 是一个队列，存储第 i 个团队当前在排队的成员（子队列）
queue<int> tq[1000];
char cmd[8];

int main()
{
    int s = 1;
    while (true) {
        int t; scanf("%d", &t);
        if (t == 0) break; // 输入 t=0 时结束
        printf("Scenario #%d\n", s++);
        
        // 读取每个团队的成员信息
        for (int i = 0; i < t; i++) {
            int n; scanf("%d", &n);
            for (int j = 0; j < n; j++) {
                int id; scanf("%d", &id);
                team[id] = i; // 建立映射关系：人员编号 -> 团队编号
            }
            // 初始化/清空上一组数据残留的团队子队列
            while (!tq[i].empty()) tq[i].pop();
        }
        
        // q 是主队列，存储当前在队伍中的团队编号（按进入顺序排列）
        queue<int> q;
        while (true) {
            scanf("%s", cmd);
            if (cmd[0] == 'S') { // STOP 指令
                break;
            } else if (cmd[0] == 'E') { // ENQUEUE 指令
                int x; scanf("%d", &x);
                int tid = team[x]; // 获取 x 所属的团队编号
                
                // 如果该团队当前没有人在排队（即子队列为空），说明该团队是新来的
                // 需要将该团队编号加入主队列
                if (tq[tid].empty()) q.push(tid);
                
                // 无论是否新来，都要将人加入到对应的团队子队列中
                // 如果是新来的，上面已经把团队加入主队列了
                // 如果不是新来的，直接插队到队友后面（即加入子队列尾部）
                tq[tid].push(x);
            } else { // DEQUEUE 指令
                if (!q.empty()) {
                    int tid = q.front(); // 获取排在主队列最前面的团队编号
                    printf("%d\n", tq[tid].front()); // 输出该团队排在最前面的成员
                    tq[tid].pop(); // 将该成员从团队子队列中移除
                    
                    // 如果该团队的所有成员都出队了（子队列变空）
                    // 则该团队从主队列中移除，后面若再有该团队成员来，需重新排到队尾
                    if (tq[tid].empty()) q.pop();
                }
            }
        }
        printf("\n"); // 每组测试数据后输出一个空行
    }
    return 0;
}

P2058

#include <cstdio>
#include <queue>
using std::queue;
const int N = 1e5 + 5;
struct Person {
	int t, id;
};
int cnt[N]; // cnt[i] i国家的人在船上有多少个
int main()
{
	queue<Person> q;
	int n; scanf("%d",&n);
	int ans=0; // 船上不同国籍数
	for (int i=1;i<=n;i++) {
		int t,k; scanf("%d%d",&t,&k);
		// 上船
		for (int j=1;j<=k;j++) {
			int x; scanf("%d",&x);
			q.push({t,x}); cnt[x]++;
			if (cnt[x]==1) { // 只有0->1说明国籍数+1
				ans++;
			}
		}
		// 一天前的人下船
		while (q.front().t <= t-86400) {
			int x=q.front().id;
			cnt[x]--;
			if (cnt[x]==0) { // 只有1->0说明国籍数-1
				ans--;
			}
			q.pop();
		}
		printf("%d\n",ans);
	}
    return 0;
}