什么是队列？

队列（queue）是一种数据结构，它的特点是只允许从队尾入队，从队列头部出队，满足先进先出的性质，即先进入队列的元素先出队列。可以把它理解为排队排在前一个人的后面。
比如队列中依次有 1 5 7 9 2，插入元素 $3$ 后会变成 1 5 7 9 2 3，再插入元素 $5$ 后变成 1 5 7 9 2 3 5。此时出队，最先进入的 $1$ 会先离开，剩下 5 7 9 2 3 5，这就是先进先出。
此外，队列只允许队首出队，新元素也只能在队尾入队,访问只能访问队首和队尾,无法从中间进行入队出队的操作也无法访问队列中间的元素。

队列（queue）的代码实现

1 2	int q[MAXN]; int head, tail;

q 数组为队列开辟需要的存储空间；MAXN 是这种写法所能承受的最大入队次数，一般要根据题目约束预留足够空间。
$head、tail$为指示队首与队尾元素的两个指针。
如果有新元素插入，就会插入到$tail$这个位置

void push(int x) {
    if (tail >= MAXN) cout << "Queue overflow（队列溢出）\n";
    else q[tail++] = x;
}

这是插入操作，我们接着给出出队操作，两个结合着来讲解。

void pop() {
    if (head == tail) cout << "Queue is empty（队列为空）\n";
    else head++;
}

解释：队列元素插入数组后就一直在数组中，我们通过的是首尾指针的增减来实现队列的还原。
比如插入 3 5 1，那么 q[0] 到 q[2] 分别存放 $3,5,1$。此时 $tail=3,head=0$，下次插入会写入 **q[3]**，而 q[head] 指向队首的 $3$。

pop 函数会增加队首指针的值。比如进行一次出队后，$head$ 增加为 $1$，指向 q[1]，也就是 $5$。已经出队的 $3$ 仍留在数组里，但不再属于队列的有效区间；第二次出队后，$head=2$，指向元素 $1$。
如果再进行一次出队，此时已经进行三次出队，head = tail = 3,那么队列为空。
这样我们便实现了出队和入队的操作，下面给出访问队首的操作。

int front() {
    if (head == tail) {
        cout << "Queue is empty（队列为空）\n";
        return -1; // 队列为空返回-1，此处也可以返回别的数，因为这并不代表一个对内元素，只代表“空队列”这个概念
    }
    return q[head];
}

接下来我们给出一道Luogu例题：https://www.luogu.com.cn/problem/P1996 大家可以在上面自测代码。

约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例输入

10 3

样例输出

1	3 6 9 2 7 1 8 5 10 4

对于这道问题，我们发现会形成一个所谓的约瑟夫环，报数时候如果报的数字不是$m$,那么就可以让把队首放到队尾，通过访问队首元素并将其复制到队尾然后再队首出队实现。报完$m - 1$次后，开始队首出队，出队前输出队首，然后接着循环即可。代码如下

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

const int MAXN = 10000007;
int q[MAXN], head, tail;

void push(int x) { q[tail++] = x; }
void pop() { head++; }
int front() { return q[head]; }

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) push(i);
    while (head != tail) {
        for (int i = 1; i < m; i++) {
            push(front());
            pop();
        }
        cout << front() << ' ';
        pop();
    }
    return 0;
}

我们补充一个访问队尾元素的代码

int back() {
    if (head == tail) {
        cout << "Queue is empty（队列为空）\n";
        return -1;
    }
    return q[tail - 1];
}

需要注意的一点，如果这里我们使用的头文件库有queue*或者是包含了该头文件的万能头bits/stdc++.h,数组的命名就不能使用queue。可以使用q或者其他名字来命名数组。那是为什么呢？
这里我们引出一个头文件queue中自带的现成的队列，使用STL来进行操作。

STL中的队列（queue）

#include <queue>     // 队列所需要的头文件
queue<int> q;       // 建立一个内部元素类型为 int 的队列
q.push(x);          // 将 x 插入队尾
q.pop();            // 弹出队首
q.front();          // 访问队首
q.back();           // 访问队尾
q.size();           // 查询元素个数
q.empty();          // 查询队列是否为空

特别注意： q.empty()为空返回真
接着我们使用STL中的队列来重新做一下这道题目

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);
    while (!q.empty()) {
        for (int i = 1; i < m; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}

双端队列（deque）

文章的最后我们再给出一个STL中自带的双端队列（deque）,支持队首队尾都能删除和插入元素，用法如下

deque<int> q;       // 建立双端队列
q.push_back(x);     // 在队尾插入元素
q.push_front(x);    // 在队首插入元素
q.pop_back();       // 移除队尾元素
q.pop_front();      // 移除队首元素
q.front();          // 访问队首
q.back();           // 访问队尾
q.size();           // 查询元素个数
q.empty();          // 查询队列是否为空

总结与常见问题

常见问题

head == tail 为什么表示空队列？ 因为 head 指向当前队首，tail 指向下一个可插入位置；两者重合时，中间没有有效元素。
数组模拟队列为什么可能“假溢出”？ 普通写法只让指针向后移动，出队后前面的空间不会复用。需要长期反复入队、出队时应改用循环队列。
调用 STL 的 front 或 pop 前要注意什么？ 必须先确认队列非空，否则行为未定义。
queue、deque 和 priority_queue 怎么选？ 先进先出用 queue，两端都要操作用 deque，反复取得最值用 priority_queue。

复杂度分析

普通队列的入队、出队、访问队首：时间复杂度均为 $O(1)$。
双端队列在两端插入或删除：时间复杂度均为 $O(1)$。
约瑟夫问题的队列模拟：时间复杂度与实际报数次数有关，最坏可写作 $O(nm)$，空间复杂度 $O(n)$。