四种队列数据结构：普通队列、循环队列、优先队列和双端队列。涵盖定义、基本操作、实现方式（结构体/数组/STL）及典型例题。包括机器翻译、班级值日表、数列极差及滑动窗口问题。重点讲解 FIFO 特性、循环处理机制、堆排序原理及单调队列优化。适合学习数据结构基础及算法竞赛入门。
队列是一种**先进先出（FIFO, First In First Out）**的线性数据结构，类似于生活中排队等候的场景——先来的人先接受服务，后来的人只能排在队尾等待。这种直观的规则决定了队列的核心特性：。
从结构上看，队列是一种操作受限的线性表，它允许在表的一端（称为队尾）进行插入操作，在另一端（称为队头）进行删除操作。这意味着元素进入队列时只能从队尾加入，离开队列时只能从队头移除，任何不在队头的元素都无法被直接访问，必须等到它前面的所有元素都出队后，才能成为新的队头。这种'先进先出'的机制，使得队列天然适合处理需要按顺序处理的场景。
队列的实现方式灵活多样，既可以使用数组（静态队列，通常实现为循环队列以提高空间利用率），也可以使用链表（动态队列）来构建。数组实现简单高效，访问速度快，但需要预先分配固定大小的空间，通过循环队列可以避免'假溢出'问题；链表实现则可以动态扩展，按需分配内存，更加灵活，但每个节点需要额外的指针存储空间。
队列的应用遍布计算机科学的各个领域。在操作系统层面，任务调度队列用于管理进程和线程的执行顺序，IO 请求队列用于缓冲和管理输入输出请求；在网络通信中，数据包队列用于缓冲网络数据包，处理拥塞控制；在程序设计层面，消息队列用于进程间通信和解耦系统组件，缓冲队列用于平衡生产者和消费者的速度差异。在算法设计中，队列是广度优先搜索（BFS）的核心数据结构，广泛应用于最短路径查找、树的层序遍历等场景。此外，日常应用中的打印任务队列、键盘输入缓冲区等，底层都依赖队列来实现。
队列的优缺点同样鲜明。它的优点是实现简单、操作高效（所有基本操作均为 O(1) 时间复杂度），并且能够自然地处理具有先进先出逻辑的问题。它的缺点是访问受限——无法直接访问或修改队列中任意位置的元素，必须遵循严格的存取顺序。
总的来说，队列是一种简单而强大的数据结构，它以受限的访问方式换取了清晰的逻辑结构和高效的运行性能，是计算机科学中不可或缺的基础构件，在系统设计、算法实现和日常应用中发挥着重要作用。
队列的定义有多种格式，如下：
queue<int> q; // 创建一个内部数据为 int 的空队列
deque<int> d = {1, 2, 3, 4, 5}; // deque 是双端队列，之后会讲
queue<int> q(d); // 复制优先队列 d
// 也可以自定义底层容器
list<int> l;
queue<int, list<int>> q(l);
| 操作 | 说明 |
|---|---|
q.push(x) | q 中入队一个元素 x |
q.pop() | 弹出 q 队头的元素 |
q.front() | 返回 q 队头的元素 |
q.back() | 返回 q 队尾的元素 |
q.size() | 返回 q 的元素数量 |
q.empty() | 返回 q 是否为空 |
const int MAXN = 1e6 + 5; // 最大长度
struct Queue {
int q[MAXN], head, tail; // 队列 头指针 尾指针
Queue() {
memset(q, 0, sizeof(q)); // 清空
head = tail = 0; // 初始为空
}
void push(int x) { // 入队
q[++tail] = x;
}
void pop() { // 弹出
head++;
}
int front() { // 队首元素
return q[head + 1];
}
int back() { // 队尾元素
return q[tail];
}
int size() { // 长度
return tail - head;
}
bool empty() { // 是否为空
return head == tail;
};
};
和结构体差不多，代码就不贴了。
洛谷 P1540 [NOIP 2010 提高组] 机器翻译
给你 n 个数，如果 a_i 没在内存中出现过且内存数量小于 m，将 a_i 加入内存，否则弹出内存最后一项，将 a_i 加入内存。
使用队列来维护内存，加入内存就是 push()，弹出就是 pop()。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e3 + 5;
int m, n, a[MAXN], cnt;
bool vis[MAXN];
queue<int> q;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!vis[a[i]]) {
if (q.size() < m) {
q.push(a[i]);
vis[a[i]] = true;
} else {
vis[q.front()] = false;
q.pop();
q.push(a[i]);
vis[a[i]] = true;
}
cnt++;
}
}
cout << cnt << endl;
return 0;
}
循环队列相比普通队列唯一的区别就是——它能循环
循环队列没有特定的头文件，通常需要手打，下面给出一个范例
const int MAXN = 1e6 + 5; // 最大长度
struct CircularQueue {
int q[MAXN], head, tail, cnt; // 队列 头指针 尾指针 长度
CircularQueue() {
memset(q, 0, sizeof(q)); // 清空
head = tail = cnt = 0; // 归零
}
void push(int x) { // 入队
if (cnt == MAXN) {
return;
}
q[tail] = x;
tail = (tail + 1) % MAXN;
cnt++;
}
void pop() { // 弹出
head = (head + 1) % MAXN;
cnt--;
}
int front() { // 队首
return q[head];
}
int back() { // 队尾
return q[(tail - 1 + MAXN) % MAXN];
}
int size() { // 长度
return cnt;
}
bool empty() { // 判空
return !cnt;
}
};
循环队列没有固定操作，按上面的代码为准
| 操作 | 说明 |
|---|---|
q.push(x) | 将 x 入队（如果满了就无法入队） |
q.pop() | 删除 q 的队首元素 |
q.front() | 返回 q 的队首元素 |
q.back() | 返回 q 的队尾元素 |
q.size() | 返回 q 的元素数量 |
q.empty() | 返回 q 是否为空 |
班主任为了培养同学们的责任感，制定了一个循环值日制度。班级有 n 个同学，编号为 1 到 n。每个工作日需要安排 m 个同学值日。
值日安排规则如下：
第二天继续从新的队首开始选 m 个同学 每天从当前值日队伍的队首开始，连续选出 m 个同学担任当天的值日生 班主任想知道，前 k 天中，每天的值日生编号以及经过 k 天后，队伍中同学的顺序。
一行三个整数 n, m, k，表示： k：天数 m：每天值日人数 n：班级总人数
输出共 k+1 行： 第 k+1 行：n 个整数，表示经过 k 天后，队伍中同学的顺序（从队首到队尾） 前 k 行：每行 m 个整数，表示当天值日的同学编号（按值日顺序）
5 2 3
1 2 3 4 5 1 3 4 5 2 1
4 3 2
1 2 3 4 1 2 3 4 1 2
对于 100% 的数据：1 ≤ n ≤ 1000，1 ≤ m ≤ n，1 ≤ k ≤ 1000 对于 30% 的数据：1 ≤ n, k ≤ 100
Code
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e3 + 5;
struct Queue {
int q[MAXN];
int head, tail, cnt;
Queue() {
head = 1;
tail = 1;
cnt = 0;
}
void push(int x) {
if (cnt == MAXN) return;
q[tail] = x;
tail++;
if (tail > MAXN) tail = 1;
cnt++;
}
void pop() {
if (cnt == 0) return;
head++;
if (head > MAXN) head = 1;
cnt--;
}
int front() {
return q[head];
}
int size() {
return cnt;
}
bool empty() {
return cnt == 0;
}
int get(int i) {
int pos = head + i - 1;
if (pos > MAXN) pos -= MAXN;
return q[pos];
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
Queue q;
for (int i = 1; i <= n; i++) {
q.push(i);
}
for (int i = 1; i <= k; i++) {
int duty[MAXN];
for (int j = 1; j <= m; j++) {
duty[j] = q.front();
q.pop();
}
for (int j = 1; j <= m; j++) {
cout << duty[j];
if (j < m) cout << " ";
}
cout << endl;
for (int j = 1; j <= m; j++) {
q.push(duty[j]);
}
}
for (int i = 1; i <= q.size(); i++) {
cout << q.get(i);
if (i < q.size()) cout << " ";
}
cout << endl;
return 0;
}
优先队列的底层是二叉堆，有兴趣可以参考（十分建议）
优先队列的定义有序多种格式，如下：
priority_queue<int> q; // 默认为大根堆，从大到小
priority_queue<int, vector<int>, greater<int>> q; // greater<int> 为小根堆，从小到大
// 也可以使用自定义比较函数
struct cmp {
bool operator()(int a, int b) {
return a > b; // 小顶堆
// return a < b; // 大顶堆
}
};
priority_queue<int, vector<int>, cmp> q; // 使用自定义函数
如果是大根堆，那么在输出时会是从大到小，否则会是从小到大。 是的，优先队列在插入新元素时会自动排序！ 而且仅需 O(log(n))！这样排序就方便多了
与普通队列相同，这里不再重复展示。
佳佳的老师在黑板上写了一个由 n 个正整数组成的数列，要求佳佳进行如下操作：每次擦去其中的两个数 a 和 b，然后在数列中加入一个数 a × b + 1，如此下去直至黑板上剩下一个数为止，在所有按这种操作方式最后得到的数中，最大的为 max，最小的为 min，则该数列的极差定义为 M = max - min。
由于佳佳忙于准备期末考试，现请你帮助他，对于给定的数列，计算出相应的极差 M。
第一行为一个正整数 n 表示正整数序列的长度； 在接下来的 n 行中，每行输入一个正整数。 接下来的一行有一个 0，表示数据结束。
输出只有一行，为相应的极差 M。
3 1 2 3 0
2
对于全部数据，0 ≤ n ≤ 5 × 10^5，保证所有数据计算均在 32 位有符号整数范围内。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
priority_queue<int, vector<int>, greater<int>> maxn; // 从小到大
priority_queue<int, vector<int>, less<int>> minn; // 从大到小
int n, k;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> k;
maxn.push(k);
minn.push(k);
}
cin >> k;
while (maxn.size() > 1) {
int a = maxn.top();
maxn.pop();
int b = maxn.top();
maxn.pop();
maxn.push(a * b + 1);
}
while (minn.size() > 1) {
int a = minn.top();
minn.pop();
int b = minn.top();
minn.pop();
minn.push(a * b + 1);
}
cout << maxn.top() - minn.top() << endl;
return 0;
}
双端队列极其适合用来维护滑动窗口算法
使用双端队列需要引入头文件
#include <deque>
双端队列的定义方式有很多，如下：
deque<int> q; // 定义一个空的双端队列
deque<int> q(10); // 定义一个有 10 个元素的双端队列，初始化为 0
deque<int> q(10, 5); // 10 个元素，每个都是 5
// 类似数组的定义方式（C++ 11）
deque<int> q = {1, 2, 3, 4, 5};
deque<int> q{1, 2, 3, 4, 5}; // 5. 用数组/迭代器范围
int a[] = {1, 2, 3, 4, 5};
deque<int> q(a, a + 5); // 从数组复制
vector<int> v = {1, 2, 3, 4, 5};
deque<int> q(v.begin(), v.end()); // 从 vector 复制
// 6. 拷贝构造
deque<int> q1 = {1, 2, 3};
deque<int> q2(dq1); // 复制 q1
| 操作 | 说明 |
|---|---|
q.push_back(x) | 在 q 的尾部入队 x |
q.push_front(x) | 在 q 的前端入队 x |
q.pop_back() | 弹出 q 队尾的元素 |
q.pop_front() | 弹出 q 队首的元素 |
q.front() | 返回 q 的队首元素 |
q.back() | 返回 q 的队尾元素 |
q.size() | 返回 q 中元素的数量 |
q.empty() | 返回 q 是否为空 |
给定一个长度为 n（n<=10^6）的数组。有一个大小为 k 的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的 k 个数字。窗口每次向右滑动一个数字的距离。下面是一个例子：数组是 [1 3 -1 -3 5 3 6 7]，k = 3。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是得到滑动窗口在每个位置时的最大值和最小值。
输入包括两行。 第一行包括 n 和 k，分别表示数组的长度和窗口的大小。 第二行包括 n 个数字。
输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。
8 3 1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3 3 3 5 5 6 7
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e6 + 5;
int n, k, maxn[MAXN], minn[MAXN], a[MAXN];
deque<int> q1, q2;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
if (q1.size() && q1.front() <= i - k) {
q1.pop_front();
}
while (q1.size() && a[q1.back()] > a[i]) {
q1.pop_back();
}
q1.push_back(i);
if (i >= k - 1) {
minn[i - k + 1] = a[q1.front()];
}
}
for (int i = 1; i <= n; i++) {
if (q2.size() && q2.front() <= i - k) {
q2.pop_front();
}
while (q2.size() && a[q2.back()] < a[i]) {
q2.pop_back();
}
q2.push_back(i);
if (i >= k - 1) {
maxn[i - k + 1] = a[q2.front()];
}
}
for (int i = 1; i <= n - k + 1; i++) {
cout << minn[i] << " ";
}
cout << endl;
for (int i = 1; i <= n - k + 1; i++) {
cout << maxn[i] << " ";
}
cout << endl;
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online