队列

队列是一种 先进先出（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;
}

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说明国籍数+1ans++;}}// 一天前的人下船while (q.front().t <= t-86400) {int x=q.front().id;cnt[x]--;if (cnt[x]==0) { // 只有1->0说明国籍数-1ans--;}q.pop();}printf("%d\n",ans);}return 0;
}