队列

概念讲解

什么是队列？

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。

类比： 排队买票，先来的人先买

队列的基本操作

实现方式

数组实现（循环队列）

1234567891011121314151617181920212223const int N = 1005;
int q[N];  // 队列数组
int hh = 0, tt = -1;  // 队首、队尾指针

// 入队
void push(int x) {
    q[++tt] = x;
}

// 出队
void pop() {
    hh++;
}

// 获取队首
int front() {
    return q[hh];
}

// 判断是否为空
bool empty() {
    return hh > tt;
}

STL queue

12345678910111213141516171819202122#include <queue>
using namespace std;

queue<int> q;

// 入队
q.push(1);

// 出队
q.pop();

// 获取队首
int x = q.front();

// 获取队尾
int y = q.back();

// 判断是否为空
if (q.empty()) { ... }

// 获取大小
int sz = q.size();

STL deque（双端队列）

123456789101112131415#include <deque>
using namespace std;

deque<int> dq;

// 两端操作
dq.push_back(1);   // 队尾入队
dq.push_front(2);  // 队首入队
dq.pop_back();     // 队尾出队
dq.pop_front();    // 队首出队

// 访问
cout << dq.front() << endl;
cout << dq.back() << endl;
cout << dq[0] << endl;

经典应用

1. BFS 中的应用

123456789101112131415161718queue<pair<int, int>> q;
q.push({startX, startY});
visited[startX][startY] = true;

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (合法 && !visited[nx][ny]) {
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

2. 滑动窗口最大值

123456789101112131415161718192021222324vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    
    for (int i = 0; i < nums.size(); i++) {
        // 移除超出窗口的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // 移除比当前元素小的元素
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

3. 约瑟夫环

1234567891011121314int josephus(int n, int m) {
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);
    
    while (q.size() > 1) {
        for (int i = 0; i < m - 1; i++) {
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    
    return q.front();
}

考点分析

初赛考查方式

1. 选择题： 队列的特性

   • 例：队列的特点是什么？
   • 答：先进先出（FIFO）

2. 程序阅读： 理解队列操作过程

3. 完善程序： 补全队列代码

常见题型

• BFS
• 滑动窗口
• 模拟排队

例题精讲

例题 1：约瑟夫环

题目： n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出列，求最后剩下的人。

解答：

1234567891011121314151617181920212223#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);
    
    while (q.size() > 1) {
        for (int i = 0; i < m - 1; i++) {
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    
    cout << q.front() << endl;
    
    return 0;
}

例题 2：BFS 最短路径

题目： 求迷宫中从起点到终点的最短路径。

解答： 参考 BFS 知识点。

练习题

1. 用两个栈实现队列。

1234567891011121314151617181920212223242526272829class MyQueue {
    stack<int> in, out;
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int x = out.top();
        out.pop();
        return x;
    }
    
    int front() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        return out.top();
    }
};

2. 洛谷 P1540 机器翻译

1234567891011121314151617181920212223242526272829303132#include <iostream>
#include <queue>
#include <set>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    
    queue<int> q;
    set<int> s;
    int ans = 0;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        if (s.find(x) == s.end()) {
            ans++;
            q.push(x);
            s.insert(x);
            
            if (q.size() > m) {
                s.erase(q.front());
                q.pop();
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

3. 洛谷 P1162 填涂颜色

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[n][n];
    bool visited[n][n] = {false};
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    
    queue<pair<int,int>> q;
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    
    // 从边界上的 0 开始 BFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ((i == 0 || i == n-1 || j == 0 || j == n-1) && a[i][j] == 0) {
                q.push({i, j});
                visited[i][j] = true;
            }
        }
    }
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && a[nx][ny] == 0) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    
    // 将未访问的 0 变为 2
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 0 && !visited[i][j]) {
                a[i][j] = 2;
            }
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

易错点

⚠️ 注意：

1. 队列为空时不能 front、back 或 pop
2. STL queue 的 pop 不返回值
3. 循环队列要注意空间利用
4. BFS 用队列，DFS 用栈