队列（Queue）数据结构详解及例题

3. 手打队列

（1）使用结构体

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;
    };
}; 

（2）使用数组

和结构体差不多，代码就不贴了。

4. 例题

洛谷 P1540 [NOIP 2010 提高组] 机器翻译

题目大意

给你 n 个数，如果 a_i 没在内存中出现过且内存数量小于 m，将 a_i 加入内存，否则弹出内存最后一项，将 a_i 加入内存。

思路

使用队列来维护内存，加入内存就是 push()，弹出就是 pop()。

Code

#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;
}

二、循环队列

循环队列相比普通队列唯一的区别就是——它能循环

1. 手打循环队列

循环队列没有特定的头文件，通常需要手打，下面给出一个范例

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;
    }
}; 

2. 循环队列的基本操作

循环队列没有固定操作，按上面的代码为准

3. 例题

班级循环值日表

题目描述

班主任为了培养同学们的责任感，制定了一个循环值日制度。班级有 n 个同学，编号为 1 到 n。每个工作日需要安排 m 个同学值日。

值日安排规则如下：

1. 这 m 个同学值日后，按照他们当天值日的顺序，重新加入到队伍的队尾（保持他们的相对顺序）
2. 如此循环往复

第二天继续从新的队首开始选 m 个同学 每天从当前值日队伍的队首开始，连续选出 m 个同学担任当天的值日生 班主任想知道，前 k 天中，每天的值日生编号以及经过 k 天后，队伍中同学的顺序。

输入格式

一行三个整数 n, m, k，表示： k：天数 m：每天值日人数 n：班级总人数

输出格式

输出共 k+1 行： 第 k+1 行：n 个整数，表示经过 k 天后，队伍中同学的顺序（从队首到队尾） 前 k 行：每行 m 个整数，表示当天值日的同学编号（按值日顺序）

输入输出样例

输入 #1

5 2 3

输出 #1

1 2 3 4 5 1 3 4 5 2 1

样例解释

• 初始队伍：1 2 3 4 5
• 第 1 天：值日生 1 2 → 他们值日后到队尾，队伍变为：3 4 5 1 2
• 第 2 天：值日生 3 4 → 队伍变为：5 1 2 3 4
• 第 3 天：值日生 5 1 → 队伍变为：3 4 2 5 1（注意：值日生 5 和 1 保持顺序到队尾）
• 第 4 行输出第 3 天结束后的队伍顺序：3 4 2 5 1

输入 #2

4 3 2

输出 #2

1 2 3 4 1 2 3 4 1 2

样例解释：

• 初始：1 2 3 4
• 第 1 天：值日 1 2 3 → 队伍：4 1 2 3
• 第 2 天：值日 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;
}

三、优先队列

优先队列的底层是二叉堆，有兴趣可以参考（十分建议）

1. 优先队列的定义

优先队列的定义有序多种格式，如下：

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; // 使用自定义函数 

2. 优先队列的性质

如果是大根堆，那么在输出时会是从大到小，否则会是从小到大。 是的，优先队列在插入新元素时会自动排序！ 而且仅需 O(log(n))！这样排序就方便多了

3. 优先队列的基本函数

与普通队列相同，这里不再重复展示。

4. 例题

数列极差

题目描述

佳佳的老师在黑板上写了一个由 n 个正整数组成的数列，要求佳佳进行如下操作：每次擦去其中的两个数 a 和 b，然后在数列中加入一个数 a × b + 1，如此下去直至黑板上剩下一个数为止，在所有按这种操作方式最后得到的数中，最大的为 max，最小的为 min，则该数列的极差定义为 M = max - min。

由于佳佳忙于准备期末考试，现请你帮助他，对于给定的数列，计算出相应的极差 M。

输入格式

第一行为一个正整数 n 表示正整数序列的长度； 在接下来的 n 行中，每行输入一个正整数。 接下来的一行有一个 0，表示数据结束。

输出格式

输出只有一行，为相应的极差 M。

输入 #1

3 1 2 3 0

输出 #1

2

说明提示

对于全部数据，0 ≤ n ≤ 5 × 10^5，保证所有数据计算均在 32 位有符号整数范围内。

Code

#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;
}

四、双端队列与滑动窗口

双端队列极其适合用来维护滑动窗口算法

1. 双端队列的定义

使用双端队列需要引入头文件

#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

2. 双端队列的基本操作

3. 例题

题目描述

给定一个长度为 n（n<=10^6）的数组。有一个大小为 k 的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的 k 个数字。窗口每次向右滑动一个数字的距离。下面是一个例子：数组是 [1 3 -1 -3 5 3 6 7]，k = 3。

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

输入格式

输入包括两行。 第一行包括 n 和 k，分别表示数组的长度和窗口的大小。 第二行包括 n 个数字。

输出格式

输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。

输入 #1

8 3 1 3 -1 -3 5 3 6 7

输出 #1

-1 -3 -3 -3 3 3 3 3 5 5 6 7

Code

#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;
}